题解 P3158 【[CQOI2011]放棋子】

Log_x · 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;
}