题目链接

题目大意

有 $n$ 种颜色的求各 $k$ 个，现将其打乱为一排，并将每种颜色最左侧的球染为与这 $n$ 个颜色均不相同的白色，问最后得到的颜色数列的方案数。

$n,~k \le 2000$

分析

我们发现我们并不关心一个白色的球他原来是什么颜色，因此我们可以将每种颜色的最左侧的那个白球和右侧的 $k-1$ 个球分开考虑。进而我们发现白球和其他颜色球之间的关系只有：对于序列的每一个前缀，其出现的非白色球的颜色种类不超过白球的数量。

我们发现我们提到了两个值：“白球的数量”和“非白色球的颜色”，我们考虑以这两个值描述状态设计动态规划：$f[i][j]$ 表示对于当前前缀，共出现 $i$ 个白球和 $j$ 种其他颜色的球（每种其他颜色的球在当前前缀中均已出现 $k-1$ 次）。

考虑转移方程，一个较显然的想法是讨论当前前缀的后一个球是否是白色。对于当前状态是 $f[i][j]$ 的情况：

1. 后一个球是白色：方案数即为 $f[i-1][j]$。
2. 后一个球不是白色：上一状态对应 $f[i][j-1]$，则该球的颜色一共有 $n-j+1$ 种可能，且对于这 $k-1$ 个球，除了最左侧的球固定在前缀的后一个位置以外，其他 $k-2$ 个球可以在剩余的空位置中随意摆放。总方案数为 $f[i][j-1] \times (n-j+1) \times \binom {n \times k - i - (j-1) \times (k-1)-1} {k-2}$。

代码

View on GitHub

/**
 * @author Macesuted (i@macesuted.moe)
 * @copyright Copyright (c) 2021
 * @brief
 *      My Solution: https://macesuted.moe/article/agc002f
 */

#include <bits/stdc++.h>
using namespace std;

template <typename T>
inline T read() {
    T x = 0, f = 1;
    char c = getchar();
    for (; c < '0' || c > '9'; c = getchar())
        if (c == '-') f = -1;
    for (; c <= '9' && c >= '0'; c = getchar())
        x = x * 10 + (c & 15);
    return x * f;
}

#define maxn 2005
#define maxv 4000005
#define mod 1000000007

long long f[maxn][maxn], fac[maxv], ifac[maxv];

long long Pow(long long a, long long x) {
    long long ans = 1;
    while (x) {
        if (x & 1) ans = ans * a % mod;
        a = a * a % mod;
        x >>= 1;
    }
    return ans;
}

inline long long C(int n, int m) { return fac[n] * ifac[m] % mod * ifac[n - m] % mod; }

int main() {
    fac[0] = ifac[0] = 1;
    for (int i = 1; i < maxv; i++) fac[i] = fac[i - 1] * i % mod;
    ifac[maxv - 1] = Pow(fac[maxv - 1], mod - 2);
    for (int i = maxv - 2; i; i--) ifac[i] = ifac[i + 1] * (i + 1) % mod;
    ios::sync_with_stdio(false);
    int n = read<int>(), k = read<int>();
    if (k == 1) {
        cout << 1 << endl;
        return 0;
    }
    f[0][0] = 1;
    for (int i = 1; i <= n; i++) {
        f[i][0] = f[i - 1][0];
        for (int j = 1; j <= i; j++)
            f[i][j] = (f[i - 1][j] + f[i][j - 1] * (n - j + 1) % mod * C(n * k - i - (j - 1) * (k - 1) - 1, k - 2)) % mod;
    }
    cout << f[n][n] << endl;
    return 0;
}