题解 AT3871 【[AGC021E] Ball Eat Chameleons】

· · 题解

既然是对球的颜色序列计数，那么就只需要考虑，对于每一个颜色序列，判断它是否可行。

假设总共喂了 R 个红球和 B 个蓝球，满足 R + B = K。

首先考虑一只变色龙在什么情况下最终才会变成红色：

  1. 它吃的红球比蓝球多。
  2. 它吃的红球和蓝球一样多（且不为 0 个），但是吃的最后一个球是蓝球。

如果 R < B，也就是红球总数比蓝球少，那么显然无解。

如果 R \ge B + N，也就是红球比蓝球还多 N 个，可以直接让每只变色龙吃的红球都比蓝球多，一定有解。

否则 B \le R < B + N，就只能让一些变色龙吃的红球和蓝球一样多，另一些变色龙红球吃的更多一些。

对于一种方案，我们进行调整：

这样调整之后，就一定是：一些变色龙吃的红球比蓝球多恰好一个，另一些一样多。

令 R 表示一个红球，B 表示一个蓝球。

也就是恰好有 R - B 只变色龙多吃一个 R，其它 N - (R - B) 只变色龙吃的一样多。

如果 R = B，也就是 R - B = 0，不存在多吃一个 R 的变色龙，那么考虑吃掉了最后一个球的变色龙，那么最后一个球必然是 B，那么去掉这个蓝球，就等价于 (R, B - 1) 的情况。

那么现在就至少有一只变色龙多吃一个 R，对于吃的一样多的变色龙，可以再调整：

如果它吃的不是恰好两个球（RB），那么可以在最后一个字符前取出一个 R 和一个 B，分给多吃了一个 R 的变色龙。

那么现在就变成了，每只吃的红球和蓝球一样多的变色龙，吃球的顺序都是 RB，它们的个数为 N - (R - B)。

然后剩下的 R - B 只变色龙，就可以直接每只多吃一个 R 然后满足条件了。

综上所述：对于 B < R < B + N 的情况，满足条件当且仅当能够取出 N - (R - B) 对 RB（有顺序）的子序列。

这等价于：对于每个前缀，这个前缀中的蓝球比红球最多多 B - (N - (R - B)) = R - N 个。
（就是说这个前缀中无法参与匹配的蓝球数量不能超过 R - N 个）

换句话说，令 R 为 +1，B 为 -1，则任意一个前缀和都应该要大于等于 -(R - N)。

可以看成从 (0, 0) 向右（R）或向上（B）走到 (R, B)，但是不能到达直线 y = x + (R - N) 的严格上方。

这是一类经典的组合问题，类似于卡特兰数的计算方法（翻转第一次碰到直线上方的部分），可以得到答案：

\binom{R + B}{R} - \binom{R + B}{2R - N + 1}

枚举 R（B = K - R）计算组合数即可得到答案。

时间复杂度为 \mathcal O (K)，评测链接。