题目链接：Project Euler 459
这是 PE 上一个难度为 \(100\%\) 的题，但实际上只要你对博弈论有一定的了解，这道题并不是那么难。
\(N\times N\) 的黑白棋盘，初始全白，两人游戏，将棋盘变全黑的人胜利，每次操作可以将这样的一个子矩阵内棋子全部翻白：
子矩阵右上角是白棋
子矩阵长度是平方数 \((1,4,9,\dots)\)
子矩阵宽度是三角形数 \((1,3,6,10,\dots)\)
对于 \(N=10^6\) 问先手第一步有多少种获胜的决策
这是个二维的棋盘游戏，实际上是两个一维游戏的组合，利用 \(\text{tartan}\) 定理，我们可以通过计算两个一维情况的 \(sg\) 值的 \(\text{nim}\) 积来快速得到二维情况的 \(sg\) 值。
我们设两个一维游戏分别为：
游戏一：一个 \(1\times N\) 的黑白棋盘，每次选择一段区间翻转，必须满足区间最右为白棋，且区间长度为平方数。
游戏二：一个 \(1\times N\) 的黑白棋盘，每次选择一段区间翻转，必须满足区间最右为白棋，且区间长度为三角形数。
显然，我们可以用 \(O(n\sqrt{n})\) 的复杂度暴力求出两个游戏中每个位置的白棋的 \(sg\) 值，分别设为 \(sg_1\) 和 \(sg_2\) 。
那么，对于二维棋盘中的一个白棋，设其位置为 \((x,y)\) ，其 \(sg\) 值 \(sg(x,y)=sg_1(x) \otimes sg_2(y)\) ，其中 \(\otimes\) 就是 \(\text{nim}\) 积的符号。由于 \(\text{nim}\) 积具有分配律，所以一个矩阵的 \(sg\) 值就是其长所在区间的 \(sg_1\) 的 \(\text{nim}\) 和（即异或和）与其宽所在区间的 \(sg_2\) 的 \(\text{nim}\) 和的 \(\text{nim}\) 积，于是整个初始局面的 \(sg\) 值就能算出来了。
接下来，根据异或的性质，我们的任务转化为统计有多少个满足条件的子矩阵的 \(sg\) 值与初始局面的 \(sg\) 值相等。显然，长和宽上可行的区间数都只有 \(O(n\sqrt{n})\) ，可以暴力算出每个区间的 \(sg\) 值，又由于 \(sg_1\) 和 \(sg_2\) 的范围是 \(O(\sqrt{n})\) 级的，所以我们只需分别在长和宽上统计出每个 \(sg\) 值对应了多少个区间，然后枚举长和宽上的 \(sg\) 值，计算其 \(\text{nim}\) 积是否和初始局面相等即可。