题目大意
在一个n行m列的棋盘里放一些彩色的棋子，使得每个格子最多放一个棋子，且不同颜色的棋子不能在同一行或者同一列。有多少种方法？
例如，n=m=3，有两个白棋子和一个灰棋子，下面左边两种方法都是合法的，但右边两种都是非法的。
题目分析
此题略难，容易想到搜索的方法，搜索此题应该也可以过，因为动规可以用记忆化搜索实现。
本题因为放一个颜色的棋子相当于将该行和该列从原棋盘中删除。
因此具有最优子结构，可以转为子问题处理。
设$f[k,i,j]$表示前$k$个颜色恰好占用了总共$i$行、$j$列的方案数。
这显然是一个类似背包的转移：
式子中的$g[k,i,j]$表示第$k$个颜色恰好占用了总共$i$行、$j$列的方案数。
接着思考$g[k][i][j]$如何转移。
首先，从$i$行$j$列中选出$a[k]$个数。
但是这样会包含许多非法状态，因为我们设定的是恰好，因此可能会有空行、空列。
不难发现非法情况其实是$g$状态的子问题，因此将他们减掉即可。（注意当$x=i,y=j$时不能转移）
当然答案可以有空行空列，所以：
容斥类的Dp还没怎么做过，要多练题总结。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
| #include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
using namespace std;
typedef long long LL;
inline const int Get_Int() {
int num=0,bj=1;
char x=getchar();
while(x<'0'||x>'9') {
if(x=='-')bj=-1;
x=getchar();
}
while(x>='0'&&x<='9') {
num=num*10+x-'0';
x=getchar();
}
return num*bj;
}
const LL mod=1000000009;
int n,m,c,a[15];
LL C[1005][1005],f[15][35][35],g[15][35][35],ans=0;
int main() {
n=Get_Int();
m=Get_Int();
c=Get_Int();
for(int i=1; i<=c; i++)a[i]=Get_Int();
C[0][0]=1;
for(int i=1; i<=n*m; i++) {
C[i][0]=C[i][i]=1;
for(int j=1; j<=i; j++)C[i][j]=(C[i-1][j-1]+C[i-1][j])%mod;
}
for(int k=1; k<=c; k++)
for(int i=1; i<=n; i++)
for(int j=1; j<=m; j++) {
if(i*j<a[k]||max(i,j)>a[k])continue;
g[k][i][j]=C[i*j][a[k]];
for(int x=1; x<=i; x++)
for(int y=1; y<=j; y++)
if(!(x==i&&y==j))g[k][i][j]=(g[k][i][j]-(g[k][x][y]*C[i][x]%mod*C[j][y]%mod)%mod+mod)%mod;
}
f[0][0][0]=1;
for(int k=1; k<=c; k++)
for(int i=1; i<=n; i++)
for(int j=1; j<=m; j++) {
if(i*j<a[k])continue;
for(int x=0; x<i; x++)
for(int y=0; y<j; y++)
f[k][i][j]=(f[k][i][j]+f[k-1][x][y]*g[k][i-x][j-y]%mod*C[i][x]%mod*C[j][y]%mod)%mod;
}
for(int i=1; i<=n; i++)
for(int j=1; j<=m; j++)
ans=(ans+f[c][i][j]*C[n][i]%mod*C[m][j]%mod)%mod;
printf("%lld\n",ans);
return 0;
}
|
