ARC091D Strange Nim

题意：有 堆石子，每堆有 个石子和一个常数 ，两人轮流操作，每次可以从任意一堆（假设为第 堆）石子中取出至少一个至多 个。

不能操作者输。问是否先手必胜。

，，时限 。

---

这是经典的 和问题，求出每一堆的 函数然后异或即可。

对于一堆石子 ，其后继状态为 。

我们将 相同的一组状态一起研究。

对于状态 ，一步最多拿走的石子数目均为 。

显然状态 都是无法操作的，故 值为 。

打表不难看出 。

而 达到了后继状态总数，这说明 为 的排列。

考虑 ，其后继状态为 ，其中 达到了后继状态数，无贡献。

其他部分 相当于 的排列去掉了 ，故有 。

进一步考虑 ，能发现是 的排列去掉了 ，故有

依次类推，则有 。

能写出如下递推公式：

进一步地， ，后继状态为 ，正是 的排列，于是 ，能归纳证明结论。

---

若根据上述公式直接计算 函数，复杂度较劣。

考虑在转移中将 相等的步骤一起做。

对 ，记 ，找出最大的 使得 次转移都是第三种情况。

即 ，则 。

这 次转移都是第三种情况，所以可以直接令 。

考虑复杂度，当 ， 本身就 。

当 ， 只有 种不同取值。

综上，总杂度为 。