Luogu2490 [SDOI2011] 黑白棋

题意：有一个 的棋盘，其中有 颗棋子。

一半是黑色，一半是白色，最左侧的棋子是白色，最右侧的棋子是黑色，相邻的棋子颜色不同。

小 A 可以移动白色棋子，小 B 可以移动黑色的棋子，其中白色不能往左，黑色不能往右。

两人轮流操作，每次可以同时操作 颗棋子。无法移动者负。

现在小 A 先手，问有多少种棋盘布局使得小 A 必胜。

答案对 取模。

，，，时限 。

---

这种题成早期 SDOI 传统艺能了都……

不难发现，将一对相邻的黑白棋之间的空位个数看做一堆石子数目，即转化为 。

总方案数为 ，故可以转为统计先手必败。

根据 的结论，问题现在转化成了 ：

用隔板将 拆分成 个整数，使得排名为奇数的（ 个）数的 和为 。

设 拆分成 个整数，使得 和为 的方案数。

则有：

其中 是将剩下的 个空位 分配到 个空隙中的方案数。

剩下的问题就是计算 了。

不难想到朴素的 : 表示还剩 未拆分，还需要拆分 个数，得到的 和为 的方案数。

可惜这样的状态量至少是 的，无法通过。

我们没有充分利用 “ 和为 ” 这一关键约束。

和的每一位是独立的，于是分位考虑。

设 为（从低到高）考虑到二进制第 位，已经使用了 颗石子，且保证所有低位上 和为 的方案数。

转移时可以枚举第 位 的个数 （需满足 ），则有转移 ：

其中 是从 堆石子中选取 堆的方案数。

最终 。

复杂度 。