HDU-4532 湫秋系列故事——安排座位 组合数学，计数DP

题意

有个\(n\) 个系分别有\(num[i]\) 个学生，这些学生排排坐，位置总数恰好等于总人数。

问任意相同系的学生不能相邻坐的方案数

分析

数据比较小，应该不会是公式，考虑一下动态规划

直接考虑排列比较麻烦，不妨在算出组合后乘上阶乘即可，因此可以先把同个系的看成一个人。

这里的\(dp\) 状态比较特殊

\(dp[i][j]\) 表示前\(i\) 个系中，有\(j\) 个位置的左右两侧是同个系的方案数。

注意这里是位置，也可以理解成两个座位中间的那一个。

考虑第\(i\) 个系，将\(num[i]\) 个学生拆分成\(k\) 组，那么这\(k\) 组学生安排到\(j\) 个位置中无论如何会引起$ num[i] -1- (k - 1)$ 个位置的左右两侧是同个系的数量增加

再考虑会引起多少个位置减少，所有这里再枚举一重，枚举\(u\) 个组插入原来的\(j\) 个位置即可。

因此，阶段：第\(i\) 个系，\(j\) 个位置

状态转移

初始化

答案

代码

ll C[505][505];
ll fac[505];
ll num[50];
ll dp[50][500];

void init() {
    C[0][0] = 1;
    for (int i = 1; i <= 500; i++) {
        C[i][0] = 1;
        for (int j = 1; j <= i; j++) C[i][j] = C[i - 1][j] + C[i - 1][j - 1], C[i][j] %= MOD;
    }
    fac[0] = 1;
    for (int i = 1; i <= 500; i++) fac[i] = fac[i - 1] * i % MOD;
}


int main() {
    init();
    int T = readint();
    int kase = 1;
    while (T--) {
        memset(dp, 0, sizeof dp);
        int n = readint();
        for (int i = 0; i < n; i++) num[i] = readll();
        dp[0][num[0] - 1] = 1;
        ll sum = num[0];
        for(int i = 1;i < n;sum += num[i++])
            for(int j = 0;j < sum;j++)
                if(dp[i - 1][j])
                    for(int k = 1;k <= num[i];k++)
                        for (int u = 0; u <= min(k, j); u++) {
                            ll tmp = dp[i - 1][j];
                            tmp = ((tmp * C[j][u]) % MOD * (C[num[i] - 1][k - 1] * C[sum + 1 - j][k - u] % MOD)) % MOD;
                            dp[i][j - u + num[i] - 1 - (k - 1)] += tmp;;
                            dp[i][j - u + num[i] - 1 - (k - 1)] %= MOD;
                        }
        ll res = dp[n - 1][0];
        for (int i = 0; i < n; i++) res *= fac[num[i]], res %= MOD;
        printf("Case %d: ", kase++);
        Put(res);
        puts("");
    }
}

HDU-4532 湫秋系列故事——安排座位 组合数学，计数DP

原文：https://www.cnblogs.com/hznumqf/p/13549340.html