【BZOJ4362】isn

题面

bzoj

题解

设\(f[i][j]\)表示当前在\(i\)，长度为\(j\)的最长不降子序列有多少个

这个可以用树状数组\(n^2logn\)求出

设\(g[i]\)为长度为\(i\)的不降子序列的和

则\(g[i]=\sum_{j=1}^nf[j][i]\)

最后的答案乍一看是\((n-i)!\sum_{i=1}^ng[i]\)

但是因为我们取到非降就\(break\)

所以需要容斥一下

不难想到

\[ans_i=(n-i)!\sum_{i=1}^ng[i]-(n-i-1)!g[i+1]*(i+1)\\
Ans=\sum_{i=1}^nans_i
\]

代码

#include <iostream>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cmath>

#include <algorithm>

using namespace std;

inline int gi() {

    register int data = 0, w = 1;

    register char ch = 0;

    while (!isdigit(ch) && ch != '-') ch = getchar();

    if (ch == '-') w = -1, ch = getchar();

    while (isdigit(ch)) data = 10 * data + ch - '0', ch = getchar();

    return w * data;

}

const int MAX_N = 2e3 + 5;

const int Mod = 1e9 + 7;

inline void pls(int &x, int y) { x += y; if (x >= Mod) x -= Mod; }

inline int dec(int x, int y) { x -= y; if (x < 0) x += Mod; return x; }

int N, a[MAX_N], f[MAX_N][MAX_N], c[MAX_N][MAX_N], g[MAX_N], fac[MAX_N];

int X[MAX_N], cnt;

inline int lb(int x) { return x & -x; }

void add(int *bit, int x, int v) { while (x <= cnt) pls(bit[x], v), x += lb(x); }

int sum(int *bit, int x) { int res = 0; while (x > 0) pls(res, bit[x]), x -= lb(x); return res; }

int main () {

    N = gi(); for (int i = 1; i <= N; i++) X[++cnt] = a[i] = gi();

    sort(&X[1], &X[cnt + 1]); cnt = unique(&X[1], &X[cnt + 1]) - X - 1;

    for (int i = 1; i <= N; i++) a[i] = lower_bound(&X[1], &X[cnt + 1], a[i]) - X;

    add(c[0], 1, 1);

    for (int i = 1; i <= N; i++) {

        for (int j = N; j >= 1; j--) {

            f[i][j] = sum(c[j - 1], a[i]);

            add(c[j], a[i], f[i][j]);

        }

    }

    for (int i = 1; i <= N; i++)

        for (int j = i; j <= N; j++) pls(g[i], f[j][i]);

    fac[0] = 1;

    for (int i = 1; i <= N; i++) fac[i] = 1ll * fac[i - 1] * i % Mod;

    int ans = 0;

    for (int i = 1; i <= N; i++)

        pls(ans, dec(1ll * fac[N - i] * g[i] % Mod, 1ll * fac[N - i - 1] * g[i + 1] % Mod * (i + 1) % Mod));

    printf("%d\n", ans);

    return 0;

}