题解 P3158 【[CQOI2011]放棋子】

## 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 ```cpp #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; } ```