BZOJ4361 isn <容斥+DP+线段树优化>

Problem

isn

$\mathrm{Time\;Limit:\;10\;Sec}$
$\mathrm{Memory\;Limit:\;256\;MB}$

Description

给出一个长度为$n$的序列$A\;(A_1,A_2\cdots A_n)$。如果序列$A$不是非降的，你必须从中删去一个数，重复这一操作，直到$A$非降为止。求有多少种不同的操作方案，答案模$10^9+7$。

Input

第一行一个整数$n$。
接下来一行$n$个整数，描述$A$。

Output

一行一个整数，描述答案。

Sample Input

4
1 7 5 3

Sample Output

18

Hint

$1\le N\le2000$

标签：容斥 DP 线段树

Solution

用$f[i][j]$表示以$i$结尾长度为$j$的不下降子序列个数，则

$$f[i][j]=\sum_{k=1}^{i-1}[a_k\le a_i]\cdot f[k][j-1]$$

这个$\mathrm{DP}$是$n^3$的，可以用线段树优化到$O(n^2\log{n})$。

用$g[i]$表示长为$i$的不下降子序列个数，则

$$g[j]=\sum_{i=1}^{n}f[i][j]$$

令$h[i]$为最后留下的不下降序列长度为$i$的可行方案数，那么显然有$Ans=\sum_{i=1}^{n}h[i]$，考虑如何通过$g$计算$h$。
如果不考虑方案是否可行，则留下的序列有$g[i]$种选法，删除$n-i$个数有$(n-i)!$种顺序，于是所有方案（不论是否可行）的数量为$(n-i)!\times g[i]$。
从所有方案中排除不可行的方案。观察可知这样的方案一定是在剩下一个长度为$i+1$的不下降序列时多删除了一个数。剩下长度为$i+1$的不下降序列的方案数为$(n-i-1)!\times g[i+1]$，多删除的数有$i+1$种选法，于是可知不可行的方案数为$(n-i-1)!\times g[i+1]\times (i+1)$。
综上可知，$h[i]=(n-i)!\times g[i]-(n-i-1)!\times g[i+1]\times (i+1)$。然后就可以统计答案了。

总复杂度$O(n^2\log{n}+n^2+n)$。

Code

#include <bits/stdc++.h>
#define MAX_N 2000
#define P 1000000007
using namespace std;
typedef long long lnt;
template <class T> inline void read(T &x) {
    x = 0; int c = getchar(), f = 1;
    for (; !isdigit(c); c = getchar()) if (c == 45) f = -1;
    for (; isdigit(c); c = getchar()) (x *= 10) += f*(c-'0');
}
map <int, int> mp;
int n, m, a[MAX_N+5], b[MAX_N+5];
lnt f[MAX_N+5][MAX_N+5], g[MAX_N+5], ans;
lnt tr[MAX_N+5][MAX_N+5], pw[MAX_N+5] = {1};
void add(int id, int p, lnt x) {for (; p <= m; p += (p&-p)) (tr[id][p] += x) %= P;}
lnt sum(int id, int p) {lnt ret = 0; for (; p; p -= (p&-p)) (ret += tr[id][p]) %= P; return ret;}
int main() {
    read(n);
    for (int i = 1; i <= n; i++) pw[i] = pw[i-1]*i%P;
    for (int i = 1; i <= n; i++) read(a[i]), b[i] = a[i];
    sort(b+1, b+n+1), m = (int)(unique(b+1, b+n+1)-b-1);
    for (int i = 1; i <= m; i++) mp[b[i]] = i;
    for (int i = 1; i <= n; i++) a[i] = mp[a[i]];
    f[0][0] = 1, add(0, 1, 1);
    for (int i = 1; i <= n; i++)
        for (int j = i; j; j--)
            f[i][j] = sum(j-1, a[i]), 
            (g[j] += f[i][j]) %= P, 
            add(j, a[i], f[i][j]);
    for (int i = 1; i <= n; i++)
        (ans += pw[n-i]*g[i]%P) %= P, 
        (ans += P-pw[n-i-1]*g[i+1]%P*(i+1)%P) %= P;
    return printf("%lld\n", ans), 0;
}