AT Code Festival 2017 Qual B E Popping Balls

组合数学真有趣。

题意：现在有 $A + B$ 个球组成的序列，前 $A$ 个是红色的，后 $B$ 个是蓝球，你可以在开始时选定两个数 $s, t$，你可以从 $1, s, t$ 三个位置取出球。问取出球的不同序列的个数，对 $10 ^ 9 + 7$ 取模。$A, B\leq 2000$。

其实注意到我们并不能直接枚举 $s, t$ 计算，因为不同的 $s, t$ 可能得到相同的结果。考虑另外的转换方式。

首先注意到在 $len \geq t$ 的时候，$s$ 是没有意义的，因为它如果拿走的是红球，可以被 1 所替代，如果拿的是蓝球，可以被 $t$ 所替代，所以我们可以只先考虑 $t$ 取的情况。

我们想要得到最多的序列，那么我们把 $t$ 放在第一个蓝球的位置（后面还有 $B$ 个），这样位置 1 和 位置 $t$ 一共可以取 $B$ 次，然后位置 $t$ 就没有用了。注意到除了我们钦定了第一次为蓝球外，每一次我们都可以在红球和蓝球之间任意选择，这时候的选择面是最广的，可以覆盖到其他情况。

假设我们前面取了 $i$ 个蓝球，那么等到 $s$ 取的时候，和 $t$ 的情况类似，但是只剩下 $B - i$ 个蓝球了，和刚才一样，我们从 $B - i$ 次机会中选择 $j$ 种，选完$B - i$ 次过后就只剩 1 位置可以选了。

我们现在相当于是只考虑了蓝球的情况，还需要考虑红球的情况。红球有 3 个去向：在 $t$ 拿到第一个蓝球之前，在 $s$ 和 $t$ 之间，在 $s$ 选完的后面。$t$ 选择的时候消耗了 $B - i$ 个红球，$s$ 选择的时候消耗了 $B - i - j$ 个红球（消耗是指混在蓝球当中的那些红球），那么剩下了 $A - 2\times B + 2\times i + j$ 个红球可以放在三个位置。利用插板法可以得到贡献。

最后由于 $s, t$ 可能取不到一个蓝球，注意到这时的蓝球一定是一段的，贡献为 $A + 1$。

于是最后的答案为：

$$\sum_{i = 1} ^ B \sum_{j = 1} ^ {B - i} \binom Bi \binom{B - i} j \binom {A - 2\times B + 2\times i + j + 2}2 + A + 1$$

直接计算即可，时间复杂度 $O(A + B ^ 2)$。

int main()
{
	init();
	int A, B, res = 0;
	std::cin >> A >> B;
	for (int i = 1; i <= B; ++ i)
		for (int j = 1; i + j <= B; ++ j)
			res = (res + (LL) C(B - 1, i - 1) * C(B - i - 1, j - 1) % Mod
				* C(A - 2 * B + 2 * i + j + 2, 2)) % Mod;
	res = (res + A + 1) % Mod;
	std::cout << res << std::endl;
	return 0;
}