自动搬运

查看原文

来自洛谷，原作者为

	IdnadRev 你要把眼泪汇编成册

搬运于2025-08-24 22:47:54，当前版本为作者最后更新于2023-06-05 15:17:46，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

不会数位 dp 怎么办？

显然是公平组合游戏，打表知 $SG(x)=x$，证明不难。

令 $f(s,x)=\sum_{i+j<x}[i\oplus j\oplus s\oplus x=0]$，令 $s=1\oplus 2\oplus \cdots\oplus n\oplus m$，那么答案就是（$s$ 的计算只需发现异或前缀和根据 $n\bmod 4$ 分类有简单的规律）：

$$\sum_{i=1}^nf(s,i)+f(s,m)$$

对 $f(s,x)$ 打表观察可知其服从以下规律：

令 $A_n$ 为 $0\leqslant s,x<2^n$ 对应的答案表，那么有：

$$A_{n+1}=\begin{bmatrix}A_n&2A_n\\0&2^n-T(a_n)\end{bmatrix} $$

（$T(M)$ 表示矩阵 $M$ 旋转 $180\degree$，常数 $C$ 表示由 $C$ 平铺形成的矩阵）

考虑如何计算 $f(s,x)$：讨论 $(s,x)$ 在矩阵中的方位，左下是平凡的，其余都可以递归进边长除二的矩阵内解决。

我们还需计算 $f$ 一行的前缀和：类似线段树可以将其拆分成 $\log V$ 个矩阵的完整行求和，每一个问题都可以类似上面在 $\log V$ 次递归中解决。

代码很好写，复杂度 $O(T\log^2V)$。