「NOI2018模拟2」「bzoj4361」序列isn - 容斥原理+动态规划

题目大意

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

---

题目分析

把题目的删除转化为保留来做。
设$f(i,j)$表示前$i$个数保留了$j$个，且$i$必须保留的方案数。

$$f(i,j)=\sum_{k=1}^{i-1}f(k,j-1)\quad(a_k\le a_i)$$

这个转移显然可以使用树状数组来优化。

设$g(i)$为保留了$i$个的方案数。
$g(j)=\sum_{i=1}^n f(i,j)\times (n-j)!$。
乘阶乘是要算入因为删除的顺序。

由于有可能在前面就删完了就不删了，但仍然计算进了这一层，因此需要容斥一下。

---

代码

#include<bits/stdc++.h>

using namespace std;

inline int Get_Int() {
	int num=0,bj=1;
	char x=getchar();
	while(!isdigit(x)) {if(x=='-')bj=-1;x=getchar();}
	while(isdigit(x)) {num=num*10+x-'0';x=getchar();}
	return num*bj;
}

const int maxn=2005,mod=1e9+7;

void check(int &x) {x=x>=mod?x-mod:(x<0?x+mod:x);}
void Add(int &x,int v) {x+=v;check(x);}

int n,a[maxn],b[maxn],fac[maxn],f[maxn][maxn],g[maxn];

struct BIT {
	int c[maxn];
#define lowbit(x) x&(-x)
	void add(int x,int v) {for(int i=x; i<=n; i+=lowbit(i))Add(c[i],v);}
	int query(int x) {int ans=0;for(int i=x; i; i-=lowbit(i))Add(ans,c[i]);return ans;}
	void clear() {fill(c+1,c+n+1,0);}
} bit;

int main() {
	n=Get_Int();
	fac[0]=1;
	for(int i=1; i<=n; i++) {
		b[i]=a[i]=Get_Int();
		fac[i]=1ll*fac[i-1]*i%mod;
	}
	sort(b+1,b+n+1);
	int tot=unique(b+1,b+n+1)-b-1;
	for(int i=1; i<=n; i++)a[i]=lower_bound(b+1,b+tot+1,a[i])-b;
	f[0][0]=1;
	for(int i=1; i<=n; i++)f[i][1]=1;
	for(int j=2; j<=n; j++) {
		bit.clear();
		for (int i=1; i<=n; i++) {
			if(a[i-1])bit.add(a[i-1],f[i-1][j-1]);
			Add(f[i][j],bit.query(a[i]));
		}
	}
	for(int i=0; i<=n; i++)
		for(int j=0; j<=n; j++)Add(g[j],f[i][j]);
	for(int i=1; i<=n; i++)g[i]=1ll*g[i]*fac[n-i]%mod;
	int ans=0;
	for(int i=1; i<=n; i++)Add(ans,g[i]-1ll*g[i+1]*(i+1)%mod);
	printf("%d\n",ans);
	return 0;
}