「容斥+dp」[CQOI2011]放棋子

Posted on Edited on In

$Description$

在一个m行n列的棋盘里放一些彩色的棋子，使得每个格子最多放一个棋子，且不同

颜色的棋子不能在同一行或者同一列。有多少种方法？

$Solution$

  • 由于不同色的棋子不能放在同一列，每种颜色的棋子的放置是相互独立的。

    因此可以考虑dp处理。

  • 设$f[i][j][k]$：前k种颜色的棋子占领了i行j列的方案数。

    $C[i][j]$：组合数（i个中选j个）。

    设$g[i][j][k]:$k个棋子恰好占据i行j列的方案数。

    $a[k]:$第k种棋子的个数。

  • 由于一个棋子至少要占据一行一列，我们枚举$l<i,r<j$

    $f[i][j][k]=\Sigma f[l][r][k-1]× C[n-l][i-l]× C[m-r][j-r]× g[i-l][j-r][a[k]]$

  • $Explanation:$对于$f[l][r][k-1]$中已经选中的l行r列不动，从剩下的n-l行中任意选择i-l行放置棋子，列同理。

  • 其他都好办，但我们发现$g[i][j][k]$没法直接求。

  • 通过观察，我们发现在i行j列中放k个棋子的方案数很好求（$C[i*j][k]$），不合法的方案就是实际上占领的行数<i或列数<j。

  • 所以直接枚举$l<=i,r<=j(l×r<i×j)$

    $g[i][j][k]=C[i× j][k]-\Sigma g[l][r][k]× C[i][l]× C[j][r]$

$Talk\;is\;Cheap…$

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
include<cstdio>
include<cstring>
define ll long long


const ll MOD = 1e9 + 9;
int N, M, Col;
ll g35, f35[15], C910;
int main()
{
    scanf("%d%d%d", &N, &M, &Col);
	int lim = N * M;
	for (int i = 0; i <= lim; i++)
		C[i][0] = 1;
	for (int i = 1; i <= lim; i++) 
    	for (int j = 1; j <= i; j++)
        	C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]) % MOD;
        
	f[0][0][0] = 1;
	for (int k = 1; k <= Col; k++)
	{   
    	int x; scanf("%d", &x);
    	memset(g, 0, sizeof(g));
    	for (int i = 0; i <= N; i++)
        	for (int j = 0; j <= M; j++)
       	 	{
            	if (i * j < x) continue;
            	g[i][j] = C[i * j][x];
            	for (int l = 0; l <= i; l++)
                	for (int r = 0; r <= j; r++)
                	{
                    	if (l == i && r == j) continue;
                    	g[i][j] = (g[i][j] - g[l][r] * C[i][l] % MOD * C[j][r] % MOD + MOD) % MOD;
                	}
        	}
    for (int i = 1; i <= N; i++)
        for (int j = 1; j <= M; j++)
            for (int l = 0; l < i; l++)
                for (int r = 0; r < j; r++)
                {
                    if ((i - l) * (j - r) < x) continue;
                    f[i][j][k] = (f[i][j][k] + f[l][r][k - 1] % MOD * 
						g[i - l][j - r] % MOD * C[N - l][i - l] % MOD * C[M - r][j - r] % MOD) % MOD;
                }
	}

	ll Ans = 0;
	for (int i = 1; i <= N; i++)
   		for (int j = 1; j <= M; j++)  
        	Ans = (Ans + f[i][j][Col]) % MOD;
	printf("%lld", Ans); 
	return 0;
}