【20省选十联测day10】Easy Win
题意
有 \(n\) 堆石子，\(n\le 5\times 10^5\)，每堆石子有 \(a_i\) 个，\(a_i\le n\)。Alice 和 Bob 每次可以从，某一堆取至少 \(1\) 颗、至多 \(x\) 颗石子，不能取的失败。Alice 先手，问对于所有 \(1\le x\le n\)，问谁胜利。
思路
对于一堆石子，计算它的 SG 函数，因为每个状态 \(m\) 可以到达状态 \(\max(0,m-x)\sim m-1\)，所以 \(SG(m)=m\bmod (x+1)\)。对于 \(n\) 堆石子，全为 \(0\) 的必败态所有 SG 值 \(=0\)，它们异或和也是 \(0\)，对于异或和为 \(0\) 的情况，一次移动一定会使异或和非 \(0\)，对于异或和非 \(0\) 的情况，因为所有数字的值都 \(\le x\)，所以一定存在一种方案可以使异或和为 \(0\)。因此我们要求 \(\oplus SG(a_i)\)，时间是 \(O(n^2)\) 的。
对于每个 \(x\) 都重新求一遍 \(\oplus a_i \bmod (x+1)\) 十分浪费时间。设 \(y=x+1\)，求 \(\oplus a_i \bmod y\)。首先如果有两个相等的 \(a\)，因为是异或所以直接消掉。因此我们假设所有 \(a_i\) 互不相同。把它拍到值域上，\(b_j\) 表示是否存在 \(a_i=j\)。
上面那个式子要取模，十分麻烦，我们把它变成 \(\oplus a_i - y \lfloor \frac{a_i}{y} \rfloor\)，对于每个 \(y\)，整除分块处理，块数加起来是个调和级数，是 \(n\log n\)。也就是我们把 \(j=[ly,ly+y)\) 的 \(b_j\) 分到一块，一块块求，每一块的 $ y \lfloor \frac{a_i}{y} \rfloor$ 相等，等于 \(ly\)。
求 \(j=[ly,ly+y)\) 每个 \(j-ly[b_j]\) 异或起来不好求，考虑拆开二进制位来算。
现在求上面这坨东西在第 \(k\) 位的贡献，即第 \(k\) 位 \(1\) 的数量奇偶性。\(ly-ly=0\)，显然地。\((ly+2^k) -ly\) 在第 \(k\) 位 \(=1\)，\((ly+2^k+2^k)-ly\) 在第 \(k\) 位 \(=0\)，\((ly+2^k+2^k+2^k)-ly\) 在第 \(k\) 位 \(=1\)，\(\dots\)
所以 \(j\) 在长度为 \(2^k\) 的值域从 \(ly\) 开始，交替为一段 \(0\)、一段 \(1\)。我们要求的 \([ly,ly+y)\)，包含若干段完整的 \(2^k\)，以及末尾可能截了一段不完整的。
那一段不完整的值域，在第 \(k\) 为的数字一定相同，所以直接前缀和判断这一段值域 \(b_j\) 的和的奇偶性就好。前面那若干个完整的段可以预处理。\(f_{i,j}\) 表示以值域上 \(i\) 开始，每 \(2^j\) 为一段，奇数段不计，偶数段的值域算上的 \(b\) 的前缀和。有 \(f_{i,j}\gets f_{i+2^{j+1},j}+sumb_{[i+2^j,i+2^{j+1})}\)。
没啦。
总结
先算 \(SG\) 函数，脱掉博弈论外壳。然后对求余整除分块一下，分类算。然后对于异或拆位算，算每一位 \(1\) 的个数奇偶性。然后预处理一下另类前缀和，然后算出另类区间和的奇偶性，然后求回异或和。时间复杂度 \(n\log^2 n\)。（整除分块和拆位各一个 \(\log\)）