题解
本题是一个 (DP) 加 容斥，容斥的式子很好推，重点是如何想到和如何推出 (DP) 部分的式子。
因为不同种颜色的棋子不能放在同一行或同一列，所以不同种的棋子是相对独立的。
据此，我们可以推出一个式子，设 (f_{i,j,k}) 表示前 (k) 种颜色占据了 (i) 行 (j) 列。
[f_{i,j,k}=sum_{l=0}^{i-1}sum_{r=0}^{j-1}f_{l,r,k-1}×g_{i-l,j-r,num_k}×(^{n-l}_{i-l})×(^{m-r}_{j-r})
]
其中 (g_{i,j,k}) 表示 (k) 个棋子占据 (i) 行 (j) 列，(num_k) 表示第 (k) 种颜色棋子的个数，后面的表示组合数。
来解释一下这个式子，其中因为 (k-1) 已经占据了 (l) 行 (r) 列，那么第 (k) 种颜色的棋子要占据 (i-l) 行 (j-r) 列。
所以这 (num_k) 颗棋子只能放在这 (i-l) 行 (j-r) 行的交汇处，所以由此我们可以得出 (g) 的式子
显然直接推不好推，所以我们要用容斥。易得 (g_{i,j,k}) 初始状态设为 ((^{i×j}_{num_k})) ，但其中有一些情况无法占据所有的行列，所以
[g_{i,j,k}=g_{i,j,k}-sum_{l=1}^{i}sum_{r=1}^{j} g_{l,r,k}×(^{i}_{l})×(^{j}_{r})[(lle i)||(rle j)]
]
最后，所有的行列不一定占据，但所有种类的棋子一定要放上，所以答案即为
[sum_{i=1}^{n}sum_{j=1}^{m}f_{i,j,c}
]
(AC kern 0.4emCODE:)
#include<bits/stdc++.h>
#define ri register int
#define p(i) ++i
using namespace std;
namespace IO{
char buf[1<<21],*p1=buf,*p2=buf;
inline char gc() {return p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++;}
inline int read() {
ri x=0,f=1;char ch=gc();
while(ch<'0'||ch>'9') {if (ch=='-') f=-1;ch=gc();}
while(ch>='0'&&ch<='9') {x=(x<<1)+(x<<3)+(ch^48);ch=gc();}
return x*f;
}
}
using IO::read;
namespace nanfeng{
#define ll long long
static const int N=33;
static const int MOD=1e9+9;
static const int CN=12;
int C[N*N][N*N],g[N][N],f[N][N][CN],n,m,c;
inline int main() {
n=read(),m=read(),c=read();
const int S=n*m;
C[0][0]=f[0][0][0]=1;
for (ri i(1);i<=S;p(i)) {
C[i][0]=1;
for (ri j(1);j<=i;p(j)) C[i][j]=(C[i-1][j]+C[i-1][j-1])%MOD;
}
for (ri k(1);k<=c;p(k)) {
ri num=read();
memset(g,0,sizeof(g));
for (ri i(1);i<=n;p(i)) {
for (ri j(1);j<=m;p(j)) {
if (i*j<num) continue;//要加上优化，显然
g[i][j]=C[i*j][num];
for (ri l(1);l<=i;p(l)) {
for (ri r(1);r<=j;p(r)) {
if (l==i&&r==j) continue;
g[i][j]=((ll)g[i][j]-(ll)g[l][r]*C[i][l]%MOD*C[j][r]%MOD+MOD)%MOD;
// printf("g[%d][%d]=%d
",i,j,g[i][j]);
}
}
}
}
for (ri i(1);i<=n;p(i)) {
for (ri j(1);j<=m;p(j)) {
for (ri l(0);l<i;p(l)) {
for (ri r(0);r<j;p(r)) {
if ((i-l)*(j-r)<num) break;
f[i][j][k]=((ll)f[i][j][k]+(ll)f[l][r][k-1]*g[i-l][j-r]%MOD*C[n-l][i-l]%MOD*C[m-r][j-r]%MOD)%MOD;
}
}
}
}
}
int ans=0;
for (ri i(1);i<=n;p(i)) {
for (ri j(1);j<=m;p(j)) ans=(ans+f[i][j][c])%MOD;
}
printf("%d
",ans);
return 0;
}
}
int main() {return nanfeng::main();}
时间复杂度 (O(n^2m^2c))