自动搬运

查看原文

来自洛谷，原作者为

	Log_x **

搬运于2025-08-24 21:45:54，当前版本为作者最后更新于2018-02-06 10:35:36，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

Solution

• 因为不同颜色的棋子不能在同一行或者同一列，所以每种颜色的棋子的摆放是相对独立的。

• 于是考虑设计这么一个状态 $f[i][j][k]$，表示用前 $k$ 种颜色的棋子占领了任意 $i$ 行 $j$ 列的方案数，则：（假设第 $k$ 种棋子有 $a[k]$ 枚）

• $f[i][j][k] = \sum \limits_{l = 0}^{i - 1} \sum \limits_{r = 0}^{j - 1}f[l][r][k - 1] \times $用 $a[k]$ 枚棋子占领 $(i - l)$ 行 $(j - r)$ 列的方案数 $\times C_{n - l}^{i - l} \times C_{m - r}^{j - r}((i - l) \times (j - r) \ge a[k])$

• 其它都好处理，但“用 $a[k]$ 枚棋子占领 $(i - l)$ 行 $(j - r)$ 列的方案数”似乎不是那么容易直接求。

• 考虑再设一个状态 $g[i][j][k]$，表示任意 $k$ 枚同色棋子占领了任意 $i$ 行 $j$ 列的方案数。

• 则 $g[i][j][k]$ 就为总方案数 - 不合法方案数（实际上有没有被占领的行或列的方案数），即：$$g[i][j][k]= C_{i \times j}^{k} - \sum \limits_{l = 1}^i \sum \limits_{r = 1}^j g[l][r][k] \times C_i^l \times C_j^r(l < i || r < j, i \times j \ge k)$$

• 我们预处理 $g[i][j][k]$，则 $f[i][j][k]$ 的转移就可表示为：$f[i][j][k] = \sum \limits_{l = 0}^{i - 1} \sum \limits_{r = 0}^{j - 1}f[l][r][k - 1] \times g[i - l][j - r][a[k]] \times C_{n - l}^{i - l} \times C_{m - r}^{j - r}((i - l) \times (j - r) \ge a[k])$

• 不一定要每行每列都占领，但棋子要全放完，答案就为 $\sum \limits_{i = 1}^n \sum \limits_{j = 1}^m f[i][j][c]$。

• 时间复杂度 $O(n^2m^2c)$。

Code

#include <iostream>
#include <cstdio>
#include <cstring>

using namespace std;

typedef long long ll;
const int Mod = 1e9 + 9;
const int N = 35, M = 15, L = 905;
int g[N][N], f[N][N][M], c[L][L];
int x, n, m, C, Ans;

int main()
{		
	scanf("%d%d%d", &n, &m, &C);

	const int tmp = n * m;
	for (int i = 0; i <= tmp; ++i)
		c[i][0] = 1;
	for (int i = 1; i <= tmp; ++i)
		for (int j = 1; j <= i; ++j)
			c[i][j] = (c[i - 1][j] + c[i - 1][j - 1]) % Mod;
	
	f[0][0][0] = 1;
	for (int k = 1; k <= C; ++k) 
	{
		scanf("%d", &x);
		memset(g, 0, sizeof(g));
		for (int i = 1; i <= n; ++i)
			for (int j = 1; j <= m; ++j)
			if (i * j >= x)
			{
				g[i][j] = c[i * j][x];
				for (int l = 1; l <= i; ++l)
					for (int r = 1; r <= j; ++r)
					if (l < i || r < j)
						g[i][j] = ((ll)g[i][j] - (ll)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)
					{
						int tx = i - l, ty = j - r;
						if (tx * ty >= x)
							(f[i][j][k] += (ll)f[l][r][k - 1] * g[tx][ty] % Mod 
							* c[n - l][tx] % Mod * c[m - r][ty] % Mod) %= Mod;
					}
	}
	
	for (int i = 1; i <= n; ++i)
		for (int j = 1; j <= m; ++j)
			(Ans += f[i][j][C]) %= Mod;
	printf("%d\n", Ans);
	return 0;
}