「Bzoj 3294」「CQOI2011」放棋子 (组合计数DP)

BZOJ 3294
题意：在一个$n$行$m$列的棋盘里放$c$种不同色的棋子（每种有$c_i$个），使得每个格子最多放一个棋子，且不同颜色的棋子不能在同一行或者同一列。有多少种方法？

本题发现其实列或者行交换不影响答案，那么我们可以设个$dp(i,j,k)$为前$k$个颜色占据了$i$行$j$列的方案。
那么可以转移
$$
dp(i,j,k)=\sum_{x=1}^i \sum_{y=1}^j dp(x,y,k-1) \times C^{i-x}_{n-x} \times C^{j-y}_{m-y} \times g(i-x,j-y,a_k)
$$
其中$a_k$为第$k$种颜色有几个棋子，$g(i,j,k)$为$k$个相同棋子占据了$i$行$j$列的方案。
考虑如何计算$g$，我们只用将不符合条件(即不占据$i$行$j$列时已经用完棋子)的情况减去即可，容易得总情况数目为$C_{ij}^n$
那么转移
$$
g(i,j,k)=C^{k}_{ij} - \sum_{x=1}^i \sum_{y=1}^j g(x,y,k) \times C^x_i \times C^y_j
$$
那么就可以递推求解了。

知识点：
1、容斥
2、dp的辅助dp数组

#include<cstdio> 
#include<cstring>
#include<algorithm>
#include<iostream>
#include<cmath>
#include<map>
#include<queue>
#include<set>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
#define fir first
#define sec second
#define mp make_pair
using namespace std;

namespace flyinthesky {

    const LL MO = 1000000009;

    LL n, m, c, jc[50000 + 5], jc_inv[50000 + 5];
    LL g[35][35], dp[35][35][15];

    LL ksm(LL a, LL b) {
        LL bs = a, ans = 1;
        while (b) {
            if (b & 1) ans = ans * bs % MO;
            bs = bs * bs % MO;
            b >>= 1;
        }
        return ans;
    }

    LL C(LL n, LL m) {
        if (n < m) return 0;
        return jc[n] * jc_inv[m] % MO * jc_inv[n - m] % MO;
    }

    void clean() {
        ms(dp, 0);
    }
    int solve() {

        clean();

        jc[0] = 1;
        for (LL i = 1; i <= 50000; ++i) jc[i] = jc[i - 1] * i % MO;
        for (LL i = 0; i <= 50000; ++i) jc_inv[i] = ksm(jc[i], MO - 2);

        cin >> n >> m >> c;
        dp[0][0][0] = 1;
        for (LL ak, o = 1; o <= c; ++o) {
            scanf("%lld", &ak);
            ms(g, 0);
            for (LL i = 1; i <= n; ++i) {
                for (LL j = 1; j <= m; ++j) {
                    g[i][j] = C(i * j, ak);
                    for (LL x = 0; x <= i; ++x) {
                        for (LL y = 0; y <= j; ++y) {
                            if (x == i && y == j) continue ;
                            LL tmp = g[x][y] * C(i, x) % MO * C(j, y) % MO;
                            g[i][j] = ((g[i][j] - tmp) % MO + MO) % MO;
                        }
                    }
                }
            }
            for (LL i = 1; i <= n; ++i) {
                for (LL j = 1; j <= m; ++j) {
                    for (LL x = 0; x <= i; ++x) {
                        for (LL y = 0; y <= j; ++y) {
                            if (x == i && y == j) continue ;
                            LL tmp = dp[x][y][o - 1] * C(n - x, i - x) % MO * C(m - y, j - y) % MO * g[i - x][j - y] % MO;
                            (dp[i][j][o] += tmp) %= MO;
                        }
                    }
                }
            }
        }

        /*for (LL i = 1; i <= n; ++i) 
        for (LL j = 1; j <= m; ++j)
        for (LL k = 1; k <= c; ++k) printf("i=%lld, j=%lld, k=%lld, dp=%lld\n", i, j, k, dp[i][j][k]);*/

        LL ans = 0;
        for (LL i = 1; i <= n; ++i) 
        for (LL j = 1; j <= m; ++j) (ans += dp[i][j][c]) %= MO;
        cout << ans;

        return 0;
    } 
}
int main() {
    flyinthesky::solve();
    return 0;
}