LOJ6503 「雅礼集训 2018 Day4」Magic

又一个二项式反演。

题意：给定 $m$ 种颜色，每种 $a_i$ 个球，共 $n$ 个球，任意排列，求恰好有 $k$ 个相邻球颜色相同的方案数，对 998244353 取模。$m\leq 2\times 10 ^ 4$，$n\leq 10 ^ 5$。

看到恰好，二项式反演，于是变为了计算钦定 $k$ 个的答案。

对于一种颜色，如果我们钦定他有 $i$ 个相邻位置相同，假设共 $a$ 个，那么方案数可以使用插板法计算，为 $\binom{a - 1}i$。

卷积不同的颜色时，我们可以直接使用 EGF，请注意，我们使用 $\binom{a - 1}i$ 的时候，已经默认这 $a - i$ 段是有序的了，于是直接计算使用 EGF，答案是正确的。

分治 NTT 卷积即可，时间复杂度 $O(n\log ^ 2 n)$，可以通过。

int main()
{
	init();
	auto solve = [&](auto &self, poly *a, int l, int r) -> poly {
		if (l == r) return a[l];
		int mid = (l + r) >> 1;
		return self(self, a, l, mid) * self(self, a, mid + 1, r);
	};
	int n, m, k;
	std::vector<poly> all;
	std::cin >> m >> n >> k;
	for (int i = 1, v; i <= m; ++ i)
	{
		scanf("%d", &v);
		poly cur(v);
		for (int i = 0; i < v; ++ i)
			cur[i] = (LL) C(v - 1, v - 1 - i) * infact[v - i] % Mod;
		all.push_back(cur);
	}
	auto g = solve(solve, all.data(), 0, (int) all.size() - 1);
	for (int i = 0; i <= n - m; ++ i) g[i] = (LL) g[i] * fact[n - i] % Mod;
	/*for (int &x : g) printf("%d ", x);
	puts("");*/
	int res = 0;
	for (int i = k, op = 1; i <= n - m; ++ i, op = Mod - op)
		res = (res + (LL) op * C(i, k) % Mod * g[i]) % Mod;
	std::cout << res << std::endl;
	return 0;
}