[关闭]
@ysner 2018-08-03T00:10:43.000000Z 字数 1667 阅读 1991

[CF285E] Positions in Permutations

DP 计数


题面

称一个的排列的完美数为有多少个满足
求有多少个长度为的完美数恰好为的排列。

解析

因为要计数,所以
显然状态中要包含一些信息:统计第个数的答案、有个满足条件、二数是否被用过。
但是如果真这样设状态,就只能隔一个数转移一次(因为得到的信息必须通过)。
边界状态不好设计啊。
然后我懵了

实际上,应该设表示在第个数中,已经填了个满足条件的数,表示是否已填,表示是否已填。
这样一切都顺理成章了。
决策三种:

这样(另外两状态不合法)

最后考虑计重问题。
这时得到的是完美数的所有方案。
包含了中的种方案。
包含了中的种方案。
于是乘上组合数容斥一波即可。

  1. #include<iostream>
  2. #include<cstdio>
  3. #include<cstdlib>
  4. #include<cstring>
  5. #include<cmath>
  6. #include<algorithm>
  7. #include<vector>
  8. #define re register
  9. #define il inline
  10. #define ll long long
  11. #define max(a,b) ((a)>(b)?(a):(b))
  12. #define min(a,b) ((a)<(b)?(a):(b))
  13. #define fp(i,a,b) for(re int i=a;i<=b;i++)
  14. #define fq(i,a,b) for(re int i=a;i>=b;i--)
  15. using namespace std;
  16. const int mod=1e9+7,N=6e5+100;
  17. int n,m;
  18. ll dp[1005][1005][2][2],C[1005][1005],ans[1005],jc[1005],anss;
  19. il ll gi()
  20. {
  21. re ll x=0,t=1;
  22. re char ch=getchar();
  23. while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();
  24. if(ch=='-') t=-1,ch=getchar();
  25. while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();
  26. return x*t;
  27. }
  28. int main()
  29. {
  30. n=gi();m=gi();
  31. C[0][0]=1;
  32. fp(i,1,n)
  33. {
  34. C[i][0]=1;
  35. fp(j,1,i) C[i][j]=(C[i-1][j-1]+C[i-1][j])%mod;
  36. }
  37. jc[0]=1;fp(i,1,n) jc[i]=(jc[i-1]*i)%mod;
  38. dp[0][0][1][0]=1;
  39. fp(i,1,n)
  40. fp(j,0,i)
  41. fp(k,0,1)
  42. fp(l,0,1)
  43. {
  44. (dp[i][j][l][0]+=dp[i-1][j][k][l])%=mod;//不管
  45. if(j&&k==0) (dp[i][j][l][0]+=dp[i-1][j-1][k][l])%=mod;//取i-1
  46. if(j) (dp[i][j][l][1]+=dp[i-1][j-1][k][l])%=mod;//取i+1
  47. }
  48. fp(i,0,n) (ans[i]+=dp[n][i][0][0]+dp[n][i][1][0])%=mod,ans[i]=ans[i]*jc[n-i]%mod;
  49. anss=ans[m];
  50. re int flag=-1;
  51. fp(i,m+1,n) anss=(anss+flag*ans[i]*C[i][m]%mod+mod)%mod,flag=-flag;
  52. printf("%lld\n",anss);
  53. return 0;
  54. }
添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注