BZOJ3294: [Cqoi2011]放棋子（计数Dp，组合数学）

题目链接

解题思路：

发现一个性质，如果考虑一个合法的方案可以将行和列都压到一起，也就是说，在占用行数和列数一定的情况下，行列互换是不会影响答案的，那么考虑使用如下方程：

$f[i][j][k]$为占领了i行j列使用了前k种颜色，由于要求全部用完，不需要枚举放入多少，考虑一个一个来添加颜色。考虑添加第k种颜色：

因为第k种颜色一定是占据了新的一行一列，所以加入第k种颜色后的行数=加入之前的行数+第k种颜色占据的行数，列数同理。

设第k种颜色的棋子有a个，那么我们只需要知道用A种颜色占据i行j列的方案数，设为$g[i][j][A]$这个可以使用容斥

转移即为$g[i][j][A]=C_{i*j}^A-\limits\sum_{a=1}^{i}\limits\sum_{b=1}^{j}g[a][b][A]*C_i^a*C_j^b$发现和A毛关系没有就舍去了这一维。

所以最后的转移就是：

$f[i][j][k]=\limits\sum_{a=1}^{i}\limits\sum_{b=1}^{j}f[i-a][i-b][k-1]*g[a][b]*C_{n-i+a}^{a}*C_{m-j+b}^{b}$

答案就是i，j的累和。

代码：

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 typedef long long lnt;

 const lnt mod=(lnt)(1e9+);

 lnt f[][][];

 lnt g[][];

 int num[];

 lnt C[][];

 int n,m,c;

 void get_g(int k)

 {

     memset(g,,sizeof(g));

     int A=num[k];

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

     {

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

         {

             if(i*j>=A)

             {

                 g[i][j]=C[i*j][A];

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

                 {

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

                     {

                         if(a==i&&b==j)continue;

                         (g[i][j]-=g[a][b]*C[i][a]%mod*C[j][b]%mod)%=mod;

                     }

                 }

             }

         }

     }

     return ;

 }

 void init(void)

 {

     C[][]=;

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

     {

         C[i][]=;

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

         {

             C[i][j]=(C[i-][j-]+C[i-][j])%mod;

         }

     }

     return ;

 }

 int main()

 {

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

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

     init();

     f[][][]=;

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

     {

         get_g(k);

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

         {

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

             {

                 if(i*j<num[k])continue;

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

                 {

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

                     {

                         (f[a][b][k]+=f[a-i][b-j][k-]*g[i][j]%mod*C[n-a+i][i]%mod*C[m-b+j][j]%mod)%=mod;

                     }

                 }

             }

         }

     }

     lnt ans();

     for(int i=;i<=n;i++)for(int j=;j<=m;j++)(ans+=f[i][j][c])%=mod;

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

     return ;

 }