题目
题目链接：https://www.luogu.com.cn/problem/P3235
小A是一个名副其实的狂热的回合制游戏玩家。在获得了许多回合制游戏的世界级奖项之后，小A有一天突然想起了他小时候在江南玩过的一个回合制游戏。
游戏的规则是这样的，首先给定一个数F，然后游戏系统会产生T组游戏。每一组游戏包含N堆石子，小A和他的对手轮流操作。每次操作时，操作者先选定一个不小于2的正整数M (M是操作者自行选定的，而且每次操作时可不一样)，然后将任意一堆数量不小于F的石子分成M堆，并且满足这M堆石子中石子数最多的一堆至多比石子数最少的一堆多1（即分的尽量平均，事实上按照这样的分石子万法，选定M和一堆石子后，它分出来的状态是固定的）。当一个玩家不能操作的时候，也就是当每一堆石子的数量都严格小于F时，他就输掉。(补充：先手从N堆石子中选择一堆数量不小于F的石子分成M堆后，此时共有N+M-1)堆石子，接下来小A从这N+M-1堆石子中选择一堆数量不小于F的石子，依此类推。
小A从小就是个有风度的男生，他邀请他的对手作为先手。小A现在想要知道，面对给定的一组游戏，而且他的对手也和他一样聪明绝顶的话，究竟谁能够获得胜利？
思路
题面直接从洛谷复制过来懒得修 LaTeX 了。
显然每一堆石子之间是独立的，考虑预处理出 (1sim 10^5) 个石子时的 (sg)，然后就可以 (O(sum n)) 回答了。
从小到大枚举石子个数，对于确定的石子数量 (i)，分成 (j) 组时会变成 (j-imod j) 堆有 (lfloor frac{i}{j}
floor) 个石子的堆，(imod j) 堆有 (lfloor frac{i}{j}
floor+1) 个石子的堆。
发现石子数量和 (lfloor frac{i}{j}
floor) 有关，考虑整除分块，假设分成 (lsim r) 堆时，石子数都是 (lfloor frac{i}{l}
floor) 和 (lfloor frac{i}{l}
floor+1)。
假设分成 (l) 组时有 (a) 个 (lfloor frac{i}{l}
floor)，(b) 个 (lfloor frac{i}{l}
floor+1)。那么分成 (l+1) 组时可以理解为将 (lfloor frac{i}{l}
floor) 个石子数量为 (lfloor frac{i}{l}
floor+1) 的石子堆中分别取出一个石子，然后扔到新的一堆中。
这个操作实质上为当 (l) 是偶数时，(a) 加上了偶数，(b) 减去了偶数；当 (l) 是奇数时，(a) 加上了奇数，(b) 加上了偶数。
由于我们在计算一种后继状态时只关心所有后继游戏 (sg) 的异或和，所以如果 (a,b) 都改变都是偶数，那么 (sg) 值不变，否则会异或上 (sg[lfloor frac{i}{l}
floor]) 和 (sg[lfloor frac{i}{l}
floor+1])。
而因为异或两次相同的数等价于没有异或，所以我们对于一组 ([l,r])，我们只需要计算 (l) 和 (l+1) 的贡献即可。
那么时间复杂度为 (O(msqrt{m}+sum n))，其中 (m=10^5)。
代码
#include <bits/stdc++.h>
using namespace std;
const int N=100010;
int Q,n,m,ans,sg[N];
bool vis[N];
int main()
{
scanf("%d%d",&Q,&m);
for (int i=m;i<=100000;i++)
{
memset(vis,0,sizeof(vis));
for (int l=2,r;l<=i;l=r+1)
{
r=i/(i/l);
for (int j=l;j<=min(r,l+1);j++)
{
int s=0;
if ((j-i%j)&1) s^=sg[i/j];
if ((i%j)&1) s^=sg[i/j+1];
vis[s]=1;
}
}
for (int j=0;vis[j];j++)
sg[i]=j+1;
}
while (Q--)
{
scanf("%d",&n);
ans=0;
for (int i=1,x;i<=n;i++)
{
scanf("%d",&x);
ans^=sg[x];
}
printf("%d ",(bool)ans);
}
return 0;
}