【BZOJ 3294】 3294: [Cqoi2011]放棋子 (DP+组合数学+容斥原理)

3294: [Cqoi2011]放棋子

Description

【BZOJ 3294】 3294: [Cqoi2011]放棋子 (DP+组合数学+容斥原理)

Input

输入第一行为两个整数nmc,即行数、列数和棋子的颜色数。第二行包含c个正整数,即每个颜色的棋子数。所有颜色的棋子总数保证不超过nm

Output

输出仅一行,即方案总数除以 1,000,000,009的余数。

Sample Input

4 2 2
3 1

Sample Output

8

HINT

N,M<=30 C<=10 总棋子数<=250

Source

【分析】

  表示一开始看错题ORZ。。以为相同颜色的不能放一起【这样怎么做??

  然后就是其实题目不是这样的、、、

  DP[i][j][k]表示决策到第k种颜色,前k种颜色一共占了i行j列的方案数。

  枚举第k行占的行数和列数,ii,jj,那么dp[i][j][k]=f[i-ii][j-jj][k-1]*B[ii][jj][k]*C[n-(i-ii)][ii]*C[m-(j-jj)][jj]

  其中C是组合数,B[ii][jj][k]表示用ii行jj列填k个东西的方案(注意B数组要满足每一行每一列都有东西,不然好像很容易算重复)

  对于B数组,我一开始用了两种方法求,都不对(超容易算重复smg,然后很内伤)

  最后感觉只有枚举这一种方法是可以求出来的,

  就是递推 B[x][y][z]=C[x*y][k]-sigma(B[i][j][k]*C[x][i]*C[y][j]) (1<=i<=x&&1<=j<=y&&(i!=x||j!=y))

  【这里是容斥吧?

  组合数学没学好所以我这题又做了很久ORZ。。

 #include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
#define Mod 1000000009
#define Maxn 910
#define LL long long LL sm[],f[][][];
int n,m,c; LL C[Maxn][Maxn]; void get_c()
{
memset(C,,sizeof(C));
for(int i=;i<=n*m;i++) C[i][]=;
for(int i=;i<=n*m;i++)
for(int j=;j<=i;j++) C[i][j]=(C[i-][j-]+C[i-][j])%Mod;
} LL B[][][];
LL get_B(int x,int y,int z)
{
if(B[x][y][z]!=-) return B[x][y][z];
if(x==&&sm[z]==) {B[x][y][z]=;return ;}
if(sm[z]<x||sm[z]<y||x*y<sm[z]) {B[x][y][z]=;return ;}
LL ans=;
ans=C[x*y][sm[z]];
for(int i=;i<=x;i++)
for(int j=;j<=y;j++)
{
if(i==x&&j==y) continue;
// ans++;
LL X=get_B(i,j,z)%Mod,
Y=(C[x][i]*C[y][j])%Mod;
ans=ans-X*Y;ans%=Mod;
ans=(ans+Mod)%Mod;
}
// printf("B[%d][%d][%d]=%d\n",x,y,z,ans);
/*for(int i=1;i<=z;i++)
ans=(ans+get_B(x-1,y,z-i)*C[y][i])%Mod;
printf("B[%d][%d][%d]=%d\n",x,y,z,ans);*/ /*ans=C[n*m][x];ans%=Mod;
ans-=C[(n-1)*m][x]*n;ans%=Mod;
ans-=C[n*(m-1)][x]*m;ans%=Mod;
ans+=C[(n-1)*(m-1)][x]*n*m;ans%=Mod;
ans=(ans+Mod)%Mod;*/
B[x][y][z]=ans;
return ans;
} int main()
{
scanf("%d%d%d",&n,&m,&c);
for(int i=;i<=c;i++) scanf("%d",&sm[i]);
get_c();
memset(f,,sizeof(f));
memset(B,-,sizeof(B));
f[][][]=;
LL ans=;
for(int i=;i<=n;i++)
for(int j=;j<=m;j++)
for(int k=;k<=c;k++) get_B(i,j,k);
for(int k=;k<=c;k++)
{
for(int i=;i<=n;i++)
for(int j=;j<=m;j++)
{
for(int ii=;ii<=i;ii++)
for(int jj=;jj<=j;jj++)
{
LL X=(C[n-(i-ii)][ii]*C[m-(j-jj)][jj])%Mod,
Y=(f[i-ii][j-jj][k-]*B[ii][jj][k])%Mod;
f[i][j][k]=(f[i][j][k]+X*Y)%Mod;
} // f[i][j][k]=(f[i][j][k]+(C[n-(i-ii)][ii]*C[m-(j-jj)][jj])%Mod*(f[i-ii][j-jj][k-1]*C[ii*jj][sm[k]])%Mod)%Mod;
if(k==c) ans=(ans+f[i][j][k])%Mod;
// printf("f[%d][%d][%d]=%lld\n",i,j,k,f[i][j][k]);
}
}
printf("%lld\n",ans);
return ;
}

屏蔽掉的是一开始两种错误方法。。

2017-03-21 08:28:26

上一篇:EditText属性描述


下一篇:黄聪:将自己开发的插件发布到WordPress官方插件站(转)