隐藏
「NOI2018模拟2」「bzoj4361」序列isn - 容斥原理+动态规划 | Bill Yang's Blog

路终会有尽头,但视野总能看到更远的地方。

0%

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

题目大意

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


题目分析

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

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

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

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


代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
#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;
}
姥爷们赏瓶冰阔落吧~