【数学记录】P9387 [THUPC 2023 决赛] 巧克力

· · 题解

不会数位 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)。