ARC061F Card Game for Three

组合数学推式子题目。

题意：三个人面前分别有 $n, m, k$ 张牌，每张牌写着 1、2 或 3，从第一个人开始拿自己面前的牌，牌上写的什么下一个就该谁拿，当本该一个人拿时却没有牌时，这个人就获胜。求所有的牌的方案中，第一个人胜利的方案有多少种。$n, m, k\leq 3\times 10 ^ 5$。

我们考虑将取牌的序列拿出来看。除了第一次拿一张牌没有一个 1，后面每次都需要前面的人拿出一个 1，这样拿出 $n$ 个 1 后第一个人就胜利了。

于是我们得到的取牌的序列就是前面有 $n$ 个 1，然后前面不能多于 $m$ 个 2，$k$ 个 3。

枚举前面非 1 的个数，我们就可以得到：

$$ans = \sum_{i = 0} ^ {m + k} 3 ^ {m + k - i}\binom{i + n - 1}i \sum_{j = i - k} ^ m \binom ij$$

注意可能不合法，那么组合数为 0。

现在我们得到了 $O(n ^ 2)$ 的做法，但是显然不行。后面的一坨不好做，考虑递推。

设 $S(i) = \sum_{j = i - k} ^ m \binom ij$，那么裂项展开，可以得到：

$$\begin{aligned} S(i) =& \sum_{j = i - k} ^ m \binom ij\\ =& \sum_{j = i - k} ^ m \binom{i - 1}j + \sum_{j = i - k} ^ m \binom{i - 1}{j - 1}\\ S(i - 1) =& \sum_{j = i - k - 1} ^ m \binom{i - 1}{j}\\ S(i) =& 2S(i - 1) - \binom{i - 1}{i - k - 1} - \binom{i - 1}{m} \end{aligned}$$

直接递推即可，时间复杂度线性。

int main()
{
	init();
	int n, m, k;
	std::cin >> n >> m >> k;
	s[0] = 1;
	for (int i = 1; i <= m + k; ++ i)
		adj(adj(adj(s[i] = 2 * s[i - 1] - Mod) -= C(i - 1, i - k - 1)) -= C(i - 1, m));
	int res = 0;
	for (int i = 0; i <= m + k; ++ i)
		res = (res + (LL) pw3[m + k - i] * s[i] % Mod * C(i + n - 1, n - 1)) % Mod;
	std::cout << res << std::endl;
	return 0;
}