CQOI 2011 放棋子

题意

有一个 \(w\times h\) 的棋盘，有 \(c\) 种颜色的棋子，第 \(i\) 种棋子有 \(a_i\) 个。他想把棋子全部摆到棋盘上，使得每个格子上至多有 \(1\) 个棋子，并且同一行同一列不能有两个不同的棋子

请求出有多少种放旗子的方案取模 \(10^9+7\)

解法

好神的 DP 啊，给我一辈子我都想不出来

设第 \(i\) 种棋子分布在了 \(x\) 行，\(y\) 列，那么这些行列一定不会有其他颜色的棋子出现

我们把这 \(x\) 行，\(y\) 列移动到矩形的边界（相当于抽出来放到一边），新问题就是原问题的一个子问题：颜色种数减少了 \(1\)，行数减少了 \(x\)，列数减少了 \(y\)

设 \(g_{i,j,k}\) 为第 \(i\) 种颜色的棋子分布在 \(j\) 行，\(k\) 列的方案数，这个可以容斥求出

\(g_{i,j,k}\) 的初值为 \(i\times j \choose a_k\)，也就是在交叉点随意选取的方案数。显然这样会有一些行和列为空，考虑把这一部分不合法的方案容斥掉，即 \(g_{i,j,k}-\sum g_{i,u,v} \ (u\leq j,v\leq k)\)

求出 \(g\) 之后就可以 DP 了，显然一种种添加某个颜色是 DP 的最好方式

设 \(f_{i,j,k}\) 为第 \(i\) 种颜色分布在 \(j\) 行，\(k\) 列的方案数，那么
\[f_{i,j,k}=f_{i-1,j-u,k-v}\times g_{a_i,u,v} \times{j\choose u} \times {k\choose v}\]
时间复杂度 \(O(N^5)\)

代码

#include <cstdio>

using namespace std;

const int MAX_N = 50;
const int mod = 1e9 + 7;

int N, M, K;

int a[MAX_N];
int f[MAX_N][MAX_N][MAX_N], g[MAX_N][MAX_N][MAX_N], C[MAX_N * MAX_N][MAX_N * MAX_N];

inline void inc(int& x, int y) { (x += y) >= mod ? x -= mod : 0; }

void get_C() {
    for (int i = 0; i <= N * M; ++i) {
        C[i][0] = 1;
        for (int j = 1; j <= i; ++j)  inc(C[i][j], C[i - 1][j] + C[i - 1][j - 1]);
    }
}

int main() {

    scanf("%d%d%d", &N, &M, &K);

    for (int i = 1; i <= K; ++i)  scanf("%d", a + i);

    get_C();

    for (int c = 1; c <= K; ++c)
        for (int i = 1; i <= N; ++i)
            for (int j = 1; j <= M; ++j) {
                g[c][i][j] = C[i * j][a[c]];
                for (int u = 0; u <= i; ++u)
                    for (int v = 0; v <= j; ++v)
                        if (u + v)
                            inc(g[c][i][j], mod - 1LL * C[i][u] * C[j][v] % mod * g[c][i - u][j - v] % mod);
            }

    for (int i = 0; i <= N; ++i)
        for (int j = 0; j <= M; ++j)  f[0][i][j] = 1;

    for (int c = 1; c <= K; ++c)
        for (int i = 1; i <= N; ++i)
            for (int j = 1; j <= M; ++j)
                for (int u = 0; u <= i; ++u)
                    for (int v = 0; v <= j; ++v)
                        if (u + v)
                            inc(f[c][i][j], 1LL * f[c - 1][i - u][j - v] * C[i][u] % mod * C[j][v] % mod * g[c][u][v] % mod);

    printf("%d\n", f[K][N][M]);

    return 0;
}