[关闭]
@ysner 2018-08-13T14:07:21.000000Z 字数 1654 阅读 2123

[CQOI2011]放棋子

数论 容斥


题面

在一个列的棋盘里放种不同色的棋子(每种有个),使得每个格子最多放一个棋子,且不同
颜色的棋子不能在同一行或者同一列。有多少种方法?

解析

被细节坑惨系列
题目输入了这三个量,于是数组中也要包含这三个量。(???)
表示前种棋子放了任意行、列。
决策是:在哪些位置填同种颜色的棋子。

于是枚举上一个状态的(表示为)。上一状态
如果设表示个同颜色棋子放了任意行、列的方案数,


表示在空着的行中选出行放棋子。同理。

怎么求呢?(卡壳处)
直接求求不出,可以换一种思路——容斥,用所有方案减去不合法方案(即有行列没填,或者可以理解为合法的局部方案)。

依式转移即可。

由于只要放完棋子而不一定要摆满行列。


注意事项:

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