放棋子：组合数/dp/容斥原理

题目传送门

啊又是一个考场上没拿到的水题，差一步！！

组合数，先打个杨辉三角吧。

显然棋子应该一种一种的放，这很dp。

而且棋子一旦放下，那么它所在的行列就只能放这种颜色的棋子了。

设dp[i][x][y]表示正在放第i种颜色的棋子，还有x行y列没有放过棋子。

我们枚举给第i种颜色的棋子一共安排xx行yy列，需要的组合数是：

从剩余的x行中选出xx行，列同理，再从xx*yy个位置里放num[i]个棋子

但是最后一个并不是简单的组合数：你要保证你的放法把拿出的xx行yy列都用到了。

这个怎么求？感觉像容斥嘛？设g[num][xx][yy]表示用num个棋子放满xx行yy列的方案数

g[num][xx][yy]=C(xx*yy,num)-∑_x=1->xx∑_y=1->yyg[num][x][y];(x!=xx||y!=yy)

没有初状态，它会用那个组合数减去若干个0给你弄出来。

没了。。。吧。。。应该都能懂了叭？

Update：为了防止某些人误解，我要说一下我的实际做法。

我的dp含义是已经用了多少行列，正向dp，最后输出dp[c][n][m]，方法当然一样。

g数组到底怎么求，本质上也是一样的。

但因为做题和写题解之间隔了一段时间（在做划艇），所以说的和代码不太一样。

也就是会出现代码和题解不完全匹配的情况。但我写的思路还是一样的。

放心啦，我不是那种从网上扒题解还不注明来源的人，纯原创哪。

 #include<cstdio>

 #define mod 1000000009

 int c[][],dp[][][],g[][][],n,m,k,num[],ans;

 int main(){

     dp[][][]=;

     scanf("%d%d%d",&n,&m,&k);

     for(int i=;i<=k;++i)scanf("%d",&num[i]);

     for(int i=;i<=;++i)c[i][]=;

     for(int i=;i<=;++i)for(int j=;j<=i;++j)c[i][j]=(c[i-][j-]+c[i-][j])%mod;

     for(int i=;i<=k;++i)for(int x=;x<=n;++x)for(int y=;y<=m;++y){

         g[i][x][y]=c[x*y][num[i]];

         for(int xx=;xx<=x;++xx)for(int yy=;yy<=y;++yy)if(xx!=x||yy!=y)

             g[i][x][y]=(g[i][x][y]-1ll*g[i][xx][yy]*c[x][xx]%mod*c[y][yy]%mod+mod)%mod;

         for(int xx=i-;xx<x;++xx)for(int yy=i-;yy<y;++yy)

             dp[i][x][y]=(dp[i][x][y]+1ll*dp[i-][xx][yy]*c[n-xx][x-xx]%mod*c[m-yy][y-yy]%mod*g[i][x-xx][y-yy]%mod)%mod;

     }

     for(int x=;x<=n;++x)for(int y=;y<=m;++y)ans=(ans+dp[k][x][y])%mod;

     printf("%d",ans);

 }

多多取模

巴特西

放棋子：组合数/dp/容斥原理

最新文章

热门文章