CQOI2011 - 放棋子

题意

给你一个 n×mn\times m 的棋盘，和 cc 种颜色的棋子，每种棋子有 aia_i 个。要求将所有棋子放到棋盘上，满足不同颜色棋子不能同行或同列。输出方案数，对 109+910^9+9 取模。

1≤n,m≤30,1≤c≤10,∑ai≤max⁡(250,n×m)1\le n,m\le 30,1\le c\le 10, \sum a_i \le \max(250, n\times m)

题解

设计 DP 状态 f(i,j,k)f(i,j,k) 表示用了 1∼k1\sim k 种颜色的所有棋子，选了 ii 行 jj 列填充的方案数。因为不同颜色棋子不能同行或同列，考虑枚举新颜色的棋子占了几行几列，这对原来棋子是无影响。

f(i,j,k)=∑l=0i−1∑r=0j−1(n−li−l)(m−rj−r)f(l,r,k−1)g(i−l,j−r,ak)f(i,j,k)=\sum_{l=0}^{i-1}\sum_{r=0}^{j-1}\binom{n-l}{i-l}\binom{m-r}{j-r}f(l,r,k-1)g(i-l,j-r,a_k)

为第 kk 种颜色选了 i−li-l 行 j−rj-r 列。从未选择的行、列中选的，故 (n−li−l)(m−rj−r)\dbinom{n-l}{i-l}\dbinom{m-r}{j-r}。

g(i−l,j−r,ak)g(i-l,j-r,a_k) 则表示在 i−li-l 行 j−rj-r 列中填 aka_k 个棋子保证每行每列至少一个棋子的方案数。

考虑求 g(i,j,k)g(i,j,k)，可以总方案减去不合法方案（有空行或空列）：

g(i,j,k)=(ijk)−∑l=1i∑r=1j(il)(jr)g(l,r,k)[l<i∨r<j]g(i,j,k) = \binom{ij}{k} -\sum_{l=1}^i \sum_{r=1}^j \binom{i}{l}\binom{j}{r} g(l,r,k) \big[l < i \vee r < j \big]

CODE

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
// [CQOI2011]放棋子
#include <bits/stdc++.h>
template <typename Tp>
inline void read(Tp& x) {
    x = 0; bool fg = 0; char ch = getchar();
    while (ch < '0' || ch > '9') { if (ch == '-') fg ^= 1; ch = getchar();}
    while (ch >= '0' && ch <= '9') x = (x << 1) + (x << 3) + (Tp)(ch ^ 48), ch = getchar();
    if (fg) x = -x;
}
template <typename Tp, typename... Args>
void read(Tp& t, Args& ...args) { read(t); read(args...); }
using namespace std;
typedef long long ll;
const int p = 1e9 + 9;
ll g[32][32];
ll f[32][32];
ll C[1000][1000];
int n, m, c, a[16];

int main() {
    read(n, m, c);
    for (int i = 1; i <= c; ++i) read(a[i]);
    C[0][0] = 1;
    for (int i = 1; i < 1000; ++i) {
        C[i][0] = 1;
        for (int j = 1; j <= i; ++j) C[i][j] = (C[i - 1][j] + C[i - 1][j - 1]) % p;
    }
    
    f[0][0] = 1;
    for (int t = 1; t <= c; ++t) {
        memset(g, 0, sizeof(g));
        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j <= m; ++j) if (i * j >= a[t]) {
                for (int l = 1; l <= i; ++l) {
                    for (int r = 1; r <= j; ++r) if (l < i || r < j) {
                        g[i][j] = (g[i][j] + C[i][l] * C[j][r] % p * g[l][r] % p) % p;
                    }
                }
                g[i][j] = (C[i * j][a[t]] - g[i][j] + p) % p;
            }
        }

        for (int i = n; i >= 0; --i) {
            for (int j = m; j >= 0; --j) {
                f[i][j] = 0;
                for (int l = 0; l < i; ++l) {
                    for (int r = 0; r < j; ++r) if ((i - l) * (j - r) >= a[t]) {
                        f[i][j] = (f[i][j] + C[n - l][i - l] * C[m - r][j - r] % p *
                        f[l][r] % p * g[i - l][j - r] % p) % p;
                    }
                }
            }
        }
    }

    ll ans = 0;
    for (int i = 1; i <= n; ++i) for (int j = 1; j <= m; ++j) ans = (ans + f[i][j]) % p;
    cout << ans << endl;
    return 0;
}