240906 说不上爱别说谎

博客标题 / 2024-09-26 / 原文

盒盒盒。这歌居然是 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;
}