盒盒盒。这歌居然是 16 年的，都过了七八年了，突然感觉自己好老（？）
感觉自己最近说话越来越像什么，cache 命中率极低且错位。我吹过你吹过的晚风～
cache 怎么念。ca - 卡，che - 车，卡车。
A. Leftmost Ball
https://atcoder.jp/contests/agc002/tasks/agc002_f
这玩意儿不难想到，相当于是给你 \(n\) 个白球和 \(n\) 种其他颜色的球，每种 \(k-1\) 个；要求对于任意前缀，白球个数 \(\ge\) 其他颜色总数的方案数。
然后就愣住了。不知道这玩意儿怎么 DP。怒贺题解之后发现新大陆。
设 \(f_{i, j}\) 表示目前选了 \(i\) 个白球，选完了 \(j\) 种其它颜色的方案数。那么肯定有 \(i\ge j\)。然后注意到状态里面是不包含位置要素的，这是因为加上了位置反而需要额外记录每种颜色选了多少个，得不偿失；不加位置状态也能转移。只需要关注还没选的 \(n-i-j\times (k-1)\) 个位置就行了。注意这些空位之间是有相对顺序的，总之挺符合直觉。
那么转移就是放白球（在最前面），和放完另一个新颜色（要求第一个在最前面）。显然有：
\[f_{i+1,j}\gets f_{i+1,j}+f_{i,j},\\ f_{i, j+1}\gets f_{i, j+1}+f_{i,j}\times C_{n-j}^1\times C_{n\times k-i-j\times(k-1)-1}^{(k-1)-1}. \]二者均须保证选掉第一个空位是为了保证不重不漏。
初始化 \(f_{0,0}=1\)，答案即为 \(f_{n,n}\)。注意 \(k=1\) 要判一下。
#include <bits/stdc++.h>
const int mod = 1e9 + 7;
int main() {
#ifdef ONLINE_JUDGE
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cout.tie(nullptr);
#else
freopen(".in", "r", stdin);
freopen(".out", "w", stdout);
#endif
int n, k;
std::cin >> n >> k;
if (k == 1) {
std::cout << 1 << '\n';
return 0;
}
std::vector<std::vector<long long> > f(n + 1, std::vector<long long> (n + 1));
std::vector<long long> fac(n * k + 1), inv(n * k + 1);
fac[0] = inv[0] = 1;
auto qkp = [](long long x, int y) {
long long res = 1;
for (; y; (x *= x) %= mod, y >>= 1)
if (y & 1)
(res *= x) %= mod;
return res;
};
fac[0] = inv[0] = 1ll;
for (int i = 1; i <= n * k; ++i) {
fac[i] = fac[i - 1] * i % mod;
inv[i] = qkp(fac[i], mod - 2);
}
auto C = [&](int n, int m) {
return fac[n] * inv[n - m] % mod * inv[m] % mod;
};
f[0][0] = 1;
for (int i = 0; i <= n; ++i)
for (int j = 0; j <= n; ++j) {
if (i + 1 <= n)
(f[i + 1][j] += f[i][j]) %= mod;
if (j + 1 <= n && i >= j + 1)
(f[i][j + 1] += f[i][j] * (n - j) % mod * C(n * k - i - j * (k - 1) - 1, k - 2) % mod) %= mod;
}
std::cout << f[n][n] << '\n';
return 0;
}