题意

https://www.luogu.org/problem/P3158

思考

设$f_{i,j,k}$为用前k种棋子，在满足条件的情况下，在i*j的棋盘上每行每列都至少有一枚棋子的总方案数。转移为：

$f_{i,j,k}=\sum_{i_1 \leq i}\sum{j_1 \leq j}{\{f_{i-i_1,j-j_1,k-1}*g_{i_1,j_1,a_k}*C(i,i_1)*C(j,j_1)\}}$

其中g的含义为正在i*j的棋盘上放k个同色的棋子，每行每列都至少有一枚棋子的总方案数。考虑g的容斥，转移为：

$g_{i,j,k}=C(i*j,k)-\sum_{i_1 \leq i}\sum_{j_1 \leq j}{\{g_{i_1,j_1,}*C(i,i_1)*C(j,j_1)\}}(i_1!=i  or  j_1!=j)$

时间复杂度为$O(n^5*k)$。

代码

 1 // luogu-judger-enable-o2
 2 #include<bits/stdc++.h>
 3 #define mod 1000000009
 4 using namespace std;
 5 typedef long long int ll;
 6 int n,m,c,a[55];
 7 ll ans,C[1005][1005],g[35][35][1005],f[35][35][15];
 8 void init()
 9 {
10     C[0][0]=1;
11     for(int i=1;i<=1000;++i)
12     {
13         C[i][0]=1;
14         for(int j=1;j<=i;++j)
15             C[i][j]=(C[i-1][j]+C[i-1][j-1])%mod;
16     }
17     for(int i=1;i<30;++i)
18         g[0][i][0]=g[i][0][0]=1;
19     for(int i=1;i<=n;++i)
20         for(int j=1;j<=m;++j)
21             for(int k=1;k<=i*j;++k)
22             {
23                 ll sum=0;
24                 for(int i1=1;i1<=i;++i1)
25                     for(int j1=1;j1<=j;++j1)
26                         if(i1*j1>=k&&(i1!=i||j1!=j))
27                             sum=(sum+g[i1][j1][k]*C[i][i1]%mod*C[j][j1]%mod)%mod;
28                 g[i][j][k]=(C[i*j][k]-sum+mod)%mod;
29             }
30 }
31 int main()
32 {
33     ios::sync_with_stdio(false);
34     cin>>n>>m>>c;
35     for(int i=1;i<=c;++i)
36         cin>>a[i];
37     init();
38     f[0][0][0]=1;
39     for(int i=1;i<=n;++i)
40         for(int j=1;j<=m;++j)
41             for(int k=1;k<=c;++k)
42                 for(int i1=0;i1<=i;++i1)
43                     for(int j1=0;j1<=j;++j1)
44                         f[i][j][k]=(f[i][j][k]+f[i1][j1][k-1]*g[i-i1][j-j1][a[k]]%mod*C[i][i1]%mod*C[j][j1]%mod)%mod;
45     for(int i=1;i<=n;++i)
46         for(int j=1;j<=m;++j)
47             ans=(ans+f[i][j][c]*C[n][i]%mod*C[m][j]%mod)%mod;
48     cout<<ans<<endl;
49     return 0;
50 }