题意：有一条长度为 的纸带，上面有 个棋子。
每次操作可以将一枚棋子向右移动若干格，但不能跨过其他棋子，棋子不能重叠。
现在有两人轮流操作，不能操作者负。
求在所有的
种初始状态中，有多少种先手必胜。
答案对 取模，，，时限 。
首先分析这个游戏先手必胜的充要条件。
将每个棋子后面的空位看作一堆石子，移动棋子时，相当于把自己的石子给了上一个棋子。
不难发现这等价于阶梯
问题，结论是 ： 若奇数阶梯上石子数的异或和非 ，则先手必胜。
问题转化成：将 个石子分成
堆（最左侧有一堆不属于任何棋子），问有多少种情况使得偶数堆石子异或和非
。
非 不太好统计，取个补集变成
。
考虑 ，设 表示已经分出 堆，使用了 个棋子，目前偶数堆异或和为 的方案数。
转移时枚举下一堆放多少，复杂度为 ，无法通过。
我们最终只关心
的情况，上述方法记录了大量无用状态。
根据位运算的性质，逐位考虑，设 表示考虑到第 位，保证此时偶数堆已确定的前 位异或和为 ，正在安排第 堆石子的第 位，目前该位异或值为 ，且用了 个棋子。
转移显然是 的，复杂度为
。已经可以通过。
然而注意到最终只关心
的情况，于是可以进一步化简：
记 ，考虑
的某一位，有两种来源，一是在某一轮种放置了这样的一位，二是进位而得。
设
表示已经从高到低考虑到了第 位，保证此时偶数堆已确定的高位异或和为
，正在安排第 堆石子的第 位，目前该位异或值为 ，欠下的进位和为 。
看起来似乎和原来的
没什么区别，但是能够发现，显然有 ，而且，若 则不可能补完进位。
所以，第三位改为记录 ，复杂度改进为 。
还可以进一步优化，注意到每一堆的地位是相同的，没必要将堆数写进状态中。于是记
表示处理完 及以上的所有位，欠下的进位和为 的方案数。
转移时枚举第 位填写的 的个数 ，有
其中 指将 个 分给 堆，满足偶数堆有偶数个 的方案数。容易预处理。
不难发现这是个加法卷积，使用 FFT 即可做到 。