BZOJ 3294: [Cqoi2011]放棋子

3294: [Cqoi2011]放棋子

Time Limit: 10 Sec Memory Limit: 128 MB
Submit: 628 Solved: 238
[Submit][Status][Discuss]

Description

Input

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

Output

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

Sample Input

4 2 2
3 1

Sample Output

HINT

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

Source

分析：

上课不好好听课的我TAT...

此题最重要的思想感觉是补集转化思想...

f[i][j][k]代表前k种颜色占据了i行j列的方案数，那么怎么转移...

f[i][j][k]=Σf[i-x][j-y][k-1]*g[x][y][k]*c[i][x]*c[j][y]

g[x][y][k]代表什么？第k种颜色刚好占据了x行y列...感觉这个转移还是很好想的...

但是问题来了...g[x][y][k]怎么求...

我们可以转化为总方案数减去不合法的方案数，也就是g[i][j][k]=c[i*j][num[k]]-Σg[x][y][k]*c[i][x]*c[j][y]...

注意边界...WA了好几次...QAQ...

代码：

 #include<algorithm>

 #include<iostream>

 #include<cstring>

 #include<cstdio>

 //by NeighThorn

 #define int long long

 using namespace std;

 const int maxn=+,MOD=1e9+;

 int n,m,co,ans,num[maxn],c[maxn*maxn][maxn*maxn],f[maxn][maxn][maxn],g[maxn][maxn][maxn];

 signed main(void){

     memset(f,,sizeof(f));

     memset(g,,sizeof(g));

     scanf("%lld%lld%lld",&n,&m,&co);

     for(int i=;i<=co;i++)

         scanf("%lld",&num[i]);

     for(int i=;i<=;i++)

         c[i][]=c[i][i]=;

     for(int i=;i<=;i++)

         for(int j=;j<i;j++)

             c[i][j]=(c[i-][j-]+c[i-][j])%MOD;

     for(int k=;k<=co;k++)

         for(int i=;i<=n;i++)

             for(int j=;j<=m;j++)

                 if(i*j>=num[k]&&max(i,j)<=num[k]){

                     g[i][j][k]=c[i*j][num[k]];

                     for(int x=;x<=i;x++)

                         for(int y=;y<=j;y++)

                             if((i-x)||(j-y))

                                 g[i][j][k]=(g[i][j][k]-g[x][y][k]*c[i][x]%MOD*c[j][y]%MOD+MOD)%MOD;

                 }

     f[][][]=;

     for(int k=;k<=co;k++)

         for(int i=;i<=n;i++)

             for(int j=;j<=m;j++)

                 if(i*j>=num[k]){

                     for(int x=;x<=i;x++)

                         for(int y=;y<=j;y++)

                             (f[i][j][k]+=f[i-x][j-y][k-]*g[x][y][k]%MOD*c[i][x]%MOD*c[j][y]%MOD)%=MOD;

                 }

     for(int i=;i<=n;i++)

         for(int j=;j<=m;j++)

             (ans+=f[i][j][co]*c[n][i]%MOD*c[m][j]%MOD)%=MOD;

     printf("%lld\n",ans);

     return ;

 }

by NeighThorn

秒客网