Link：

 

Solution：

算是发现博弈论题目的一部分套路了吧

求SG函数，然后用各种奥妙重重的方式降求解SG的复杂度

 

此题由于每一组独立，用SG函数肯定是没问题的。

 

先看暴力 $O(n^2)$ 求解SG的方式：

枚举每个$i$分成的份数$m$，只分为$i/m$和$i/m+1$两类

由于异或的自反性，只要确定这两类数的奇偶性便确定$sg[i/m]$或$sg[i/m+1]$是否计入$sg[i]$

 

观察 $O(n^2)$ 的方法，发现很多$i$的$i/m$和$i/m+1$都相同

由于多个相同的$sg[i']$是对$sg[i]$不具有贡献的，于是我们想到分组计算

有以下两条性质：

（1）可以证明，对于确定的$i$和$m$，$i/m$的数字个数不超过$2*log(i)$

（$m<sqrt(i)$时最多$log(i)$个，$sqrt(i)<m<i$时也最多$log(i)$个）

（2）$i/m == i/(m+2)$时$SG$值相同

（$i\mod m$和$m-{i\mod m}$的奇偶性保持不变）

 

于是我们分组计算，且每次只计算每组的前两个$SG$值即可

由于F不变，用记忆化搜索提高速度

Code：

#include 
     
      using namespace std;const int MAXN=1e5+10;int T,F,n,t,dat[MAXN],sg[MAXN],mex[MAXN],cnt=0;bool vis[MAXN];int get_sg(int x){    if(x
     

 

Review：

1、按$i/m$分块的套路

算是第二次遇见这样的套路了（BZOJ 2301）

再遇到对$i/m$有处理的题目，根据其值的种类不超过$2*log(n)$的性质分块处理即可

 

注意其中转移到下一块的处理技巧：$i=x/(x/i)+1$

个人认为$x/(x/i)$表示根据当前$x/i$的值找出最大的$i'$，再加一就是另一个$x/i$值了

 

2、由于计算$SG$时相同的前继状态是没有贡献的，

考虑如何消去$SG$相同的前继状态

 

3、只要有数据能重复利用，使用记忆化搜索

 

4、求SG函数时，初始值最好都设为0，防止异或-1这种情况

如果使用$vis$数组也一定要第一时间更新，防止陷入死循环