4361: isn
Time Limit: 10 Sec Memory Limit: 256 MB
Submit: 218 Solved: 126Description
给出一个长度为n的序列A(A1,A2...AN)。如果序列A不是非降的&＃xff0c;你必须从中删去一个数&＃xff0c;这一操作&＃xff0c;直到A非降为止。求有多少种不同的操作方案&＃xff0c;答案模10^9&＃43;7。Input
第一行一个整数n。接下来一行n个整数&＃xff0c;描述A。Output
一行一个整数&＃xff0c;描述答案。
Sample Input
4
1 7 5 3Sample Output
18HINT
1<&＃61;N<&＃61;2000Source
【分析】
考虑倒着想。
你倒数第一步做之前还不是非降&＃xff0c;做完之后就非降了&＃xff0c;说明如果有一个上升序列&＃xff0c;你加倒数第一个点时候不是上升序列了&＃xff0c;前面的操作就可以任意了。
本来想保证这个的&＃xff0c;但是发现放入DP里还有一个关于长度的阶乘&＃xff0c;根本不行。
然后考虑容斥。
现在的问题是&＃xff1a;倒数第一个点x&＃xff0c;放入序列里面还是非降的&＃xff0c;这个时候不应该计算。
即操作结束在更之前。把这些不合法的减掉就好了。
g[i]表示长度为i的上升序列个数
那么贡献就是$g[i]*(n-i)!-g[i&＃43;1]*(i&＃43;1)*(n-i-1)!$
1 #include
2 #include
3 #include
4 #include
5 #include
6 using namespace std;
7 #define Maxn 2010
8 #define Mod 1000000007
9 // #define LL long long
10
11 int f[Maxn][Maxn],g[Maxn],fac[Maxn],c[Maxn],a[Maxn];
12
13 struct node {int x,id;}t[Maxn];
14 bool cmp(node x,node y) {return x.x<y.x;}
15
16 int mx;
17 void add(int x,int y)
18 {
19 for(int i&＃61;x;i<&＃61;mx;i&＃43;&＃61;i&(-i))
20 {
21 c[i]&＃61;(c[i]&＃43;y)%Mod;
22 }
23 }
24
25 int get_sum(int x)
26 {
27 int ans&＃61;0;
28 for(int i&＃61;x;i>&＃61;1;i-&＃61;i&(-i))
29 ans&＃61;(ans&＃43;c[i])%Mod;
30 return ans;
31 }
32
33 int main()
34 {
35 int n;
36 scanf("%d",&n);
37 for(int i&＃61;1;i<&＃61;n;i&＃43;&＃43;)
38 {
39 int x;scanf("%d",&x);
40 t[i].x&＃61;x;t[i].id&＃61;i;
41 }
42 sort(t&＃43;1,t&＃43;1&＃43;n,cmp);
43 mx&＃61;1;a[t[1].id]&＃61;1;
44 for(int i&＃61;2;i<&＃61;n;i&＃43;&＃43;)
45 {
46 if(t[i].x!&＃61;t[i-1].x) mx&＃43;&＃43;;
47 a[t[i].id]&＃61;mx;
48 }
49 for(int i&＃61;1;i<&＃61;n;i&＃43;&＃43;) f[1][i]&＃61;1;
50 for(int i&＃61;2;i<&＃61;n;i&＃43;&＃43;)
51 {
52 for(int j&＃61;0;j<&＃61;n;j&＃43;&＃43;) c[j]&＃61;0;
53 for(int j&＃61;1;j<&＃61;n;j&＃43;&＃43;)
54 {
55 f[i][j]&＃61;get_sum(a[j]);
56 add(a[j],f[i-1][j]);
57 }
58 }
59 for(int i&＃61;1;i<&＃61;n;i&＃43;&＃43;) for(int j&＃61;1;j<&＃61;n;j&＃43;&＃43;) g[i]&＃61;(g[i]&＃43;f[i][j])%Mod;
60 fac[0]&＃61;1;for(int i&＃61;1;i<&＃61;n;i&＃43;&＃43;) fac[i]&＃61;1LL*fac[i-1]*i%Mod;
61 int ans&＃61;0;
62 ans&＃61;(ans&＃43;g[n]);
63 for(int i&＃61;1;i
64 {
65 ans&＃61;(ans&＃43;1LL*g[i]*fac[n-i]%Mod-1LL*fac[n-i-1]*g[i&＃43;1]%Mod*(i&＃43;1)%Mod)%Mod;
66 }
67 ans&＃61;(ans&＃43;Mod)%Mod;
68 printf("%d\n",ans);
69 return 0;
70 }
2017-04-20 17:01:57
京公网安备 11010802041100号