http://www.lydsy.com/JudgeOnline/problem.php?id=3294
如果一个颜色的棋子放在了第i行第j列，那这种颜色就会占据第i行第j列，其他颜色不能往这儿放
设第k种颜色的棋子有a[k]个
令g[k][i][j] 表示第k种颜色的棋子，恰好占据i行j列的方案数
g[k][i][j]=C(i*j,a[k])-Σh Σl g[h][l]*C(i,h)*C(j,l) 1<=h<=i,1<=l<=j,且满足 h!=i 或 l !=j
即 总方案数（在i*j个格子中选a[k]个） 减去 没有恰好占据i行j列的方案数
令f[k][i][j] 表示前k种颜色的棋子，放完之后，还剩下i行j列的方案数
f[k][i][j]= Σh Σl f[k-1][h][l]*g[k][h-i][l-j]*C[h][h-i]*C[l][l-j] i<h<=n,j<l<=m
即 枚举前k-1种颜色的棋子放完后，剩下h行l列，那么 第k种颜色就占据h-i行l-j列
#include<cstdio> using namespace std; const int mod=1e9+; #define min(x,y) x<y ? x : y #define N 31
#define M 11 int C[N*N][N*N]; int a[M];
long long g[M][N][N],f[M][N][N]; int main()
{
int n,m,c;
scanf("%d%d%d",&n,&m,&c);
for(int i=;i<=c;++i) scanf("%d",&a[i]);
int lim=n*m;
C[][]=;
for(int i=;i<=lim;++i)
{
C[i][]=;
for(int j=;j<=i;++j) C[i][j]=(C[i-][j-]+C[i-][j])%mod;
}
int r1,r2;
for(int k=;k<=c;++k)
{
r1=min(a[k],n);
for(int i=;i<=r1;++i)
{
r2=min(a[k],m);
for(int j=;j<=r2;++j)
if(i*j>=a[k])
{
g[k][i][j]=C[i*j][a[k]];
for(int h=;h<=i;++h)
for(int l=;l<=j;++l)
if((h!=i || l!=j) && h*l>=a[k])
{
g[k][i][j]-=g[k][h][l]*C[i][h]%mod*C[j][l]%mod;
if(g[k][i][j]<) g[k][i][j]+=mod;
}
}
}
}
f[][n][m]=;
for(int k=;k<=c;++k)
for(int i=;i<n;++i)
for(int j=;j<m;++j)
for(int h=i+;h<=n;++h)
for(int l=j+;l<=m;++l)
if((h-i)*(l-j)>=a[k])
f[k][i][j]=(f[k][i][j]+f[k-][h][l]*g[k][h-i][l-j]%mod*C[h][h-i]%mod*C[l][l-j]%mod)%mod;
int ans=;
for(int i=;i<n;++i)
for(int j=;j<m;++j)
{
ans+=f[c][i][j];
if(ans>=mod) ans-=mod;
}
printf("%d",ans);
return ;
}
3294: [Cqoi2011]放棋子
Time Limit: 10 Sec Memory Limit: 128 MB
Submit: 797 Solved: 319
[Submit][Status][Discuss]
Description
Input
输入第一行为两个整数n, m, c，即行数、列数和棋子的颜色数。
第二行包含c个正整数，即每个颜色的棋子数。
所有颜色的棋子总数保证不超过nm。
N,M<=30 C<=10 总棋子数有大于250的情况
Output
输出仅一行，即方案总数除以 1,000,000,009的余数。
Sample Input
4 2 2
3 1
3 1
Sample Output
8