AGC013D Piling Up

题意：一开始袋子中有 个黑白球，但不知道黑白色各有多少。

进行 轮操作，每次先拿出一个球，再放入黑白球各一个，再拿出一个球。

将拿出的球按顺序排列，求形成的颜色序列可能有多少种。答案对 取模。

，时限 。

---

一个自然的想法是追踪袋子的状态，由于操作取球和放球的个数一定，我们只需要记录袋子中的黑球个数，就能推断出白球个数。

将“取出一个球”或“放入一个球”都视为一次操作，将第 次操作后袋子中的黑球数记为 ，序列 刻画了袋子的状态。

观察 的差值，就能知道这次拿出来（或放进去）的是黑球还是白球。这形成一个“袋子状态序列 ”到“取球序列 ”的单射。

那么反射如何呢？将 画成折线，我们知道 只和 的“走势”有关，那么“走势”相同，但上下平移的一系列 都会产生同样的 。我们希望在这一组 中，只计入某一个。

可以发现，一组折线中，恰好有一个与 有交，于是问题变成了统计与 有交的 序列个数。

---

表示“进行了 轮操作（每轮有四次操作），目前袋子中有 个黑球，是否曾没有黑球”的方案数。

边界为 。

操作时，分三种情况讨论 ：

• 取出黑黑：黑球个数减少一个，

• 取出白白：黑球个数增加一个，

• 取出白黑：黑球个数不变，（ 时不合法）

• 取出黑白：最终黑球个数不变，但过程中黑球会先变少一个，（ 时不合法）

答案为 的和。

复杂度 。