AGC002F Leftmost Ball

Description

给你 $n$ 种颜色的球，每个球有 $k$ 个，把这 $n\times k$ 个球排成一排，把每一种颜色的最左边出现的球涂成白色（初始球不包含白色），求最终有多少种不同的颜色序列，答案对 $10^9+7$ 取模。
$1\leq n,k\leq 2\times 10^3$

Solution

这道题重要的是怎么设置状态。

很明显，我们可以先拿出来 $n$ 个白球，剩下的每种球为 $k-1$ 个，然后再考虑可以形成的不同颜色序列数量。现在的限制为——当我们第 $i$ 次选择一个未被选择过的非白色的球时，前面放的白球数量必须大于等于 $i$ 。

最常见的设状态为 $f_{i,j}$ 表示已经放了 $i$ 个白球，第 $i$ 个白球放在序列的第 $j$ 个位置的方案数。但在本题中这样子并不好做，因为从 $f_{i-1,k}\rightarrow f_{i,j}$ 时，我们似乎还需要知道前面的非白色球各用了多少个，然后乘上隔板法+容斥的系数，而我们显然不能记录前面的非白色球各用了多少个，这条路走不通、

上述方法之所以麻烦，是因为我们每次放白色球的时候，要考虑前面所有已经放过第一个球的非白色球。事实上，对于非白色球而言，只有第一个球的位置是我们关心的，那么我们每次放一种全新的非白色球就一口气把 $k-1$ 个全放进去。所以，设状态 $f_{i,j}$ 为已经放了 $i$ 个白球，以及 $j$ 种非白色球的方案数。转移时，我们考虑序列从左往右第一个非空的位置如何放球：

• 放白球。显然合法。
• 放一种全新的非白球。我们从剩余的 $n-j+1$ 个颜色中选择一个，把第一个球放在当前的空位上，剩下的 $k-2$ 个球可以任意放在所有剩下的位置里（因为左边均已满）。

那么不难得到转移方程：

$f_{i,j}\leftarrow f_{i-1,j}+\binom{n\times k-i-(j-1)\times (k-1)-1}{k-2}\times f_{i,j-1}$

复杂度 $\mathcal{O}(n^2)$ 。

Code

const int N = 2e3 + 5, M = 4e6 + 5, mod = 1e9 + 7;
using namespace std;
int n, k;
int f[N][N];
int fac[M], inv[M], invf[M];
inline void Plus(int &a, int b){a += b - mod, a += (a >> 31) & mod;}
void Prework(int n){
    fac[0] = fac[1] = inv[0] = inv[1] = invf[0] = invf[1] = 1;
    for(int i = 2; i <= n; ++i)
        fac[i] = 1ll * fac[i - 1] * i % mod,
        inv[i] = 1ll * (mod - mod / i) * inv[mod % i] % mod,
        invf[i] = 1ll * inv[i] * invf[i - 1] % mod;
}
int binom(int n, int m){
    return n - m < 0 ? 0 : 1ll * fac[n] * invf[m] % mod * invf[n - m] % mod;
}
int main(){

    fin >> n >> k;
    Prework(4e6);

    if(k == 1){
        puts("1");
        return 0;
    }

    for(int i = 1; i <= n; ++i){
        f[i][0] = 1;
        for(int j = 1; j <= i; ++j)
            f[i][j] = f[i - 1][j],
            Plus(f[i][j], 1ll * f[i][j - 1] * (n - j + 1) % mod * binom(n * k - i - (j - 1) * (k - 1) - 1, k - 2) % mod);
    }

    cout << f[n][n] << endl;
    return 0;
}