题面
题解
首先我们知道一个关于除法的重要性质：对于一个固定的(i),表达式(frac{i}{m})的取值只有根号个。
因此我们考虑如何优化SG函数的求解。
观察到在取值相同的同一段中，分完之后只会有m堆取值为x 或者x + 1的石子。
因此我们不需要知道每种取值的石子具体有多少，我们只需要知道它们的堆数是奇是偶即可。
同时我们知道，在同一段中，如果m变化1，那么会产生的结果就是有x堆取值为x + 1的石堆变为取值为x，并且新增一堆取值为x的石堆。
我们稍作分析：
-
如果x是奇数。
那么由x + 1的石堆变成的x的石堆一共有x个，再加上新增的一个取值为x的石堆，就一共多出了x + 1个石堆，因为x是奇数，所以取值为x的石堆奇偶没有变化。
而取值为x + 1的石堆减少了x个，因此奇偶性发生变化。 -
如果x是偶数
由跟上面类似的推导可得，取值为x的石堆奇偶性发生变化。取值为x + 1的石堆不发生变化。
因此对于同一段而言，后继SG值最多2种。
所以我们SG值单次转移复杂度(sqrt{n})，总复杂度(nsqrt{n})
#include<bits/stdc++.h>
using namespace std;
#define R register int
#define AC 101000
int T, F, n;
int SG[AC];
bool z[AC];
inline int read()
{
int x = 0;char c = getchar();
while(c > '9' || c < '0') c = getchar();
while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
return x;
}
void dfs(int x)
{
if(z[x]) return ;
z[x] = true;
if(x < F) {SG[x] = 0; return ;}
bool vis[840];//因为后继状态最多六七百，所以SG不会超过800
memset(vis, 0, sizeof(vis));
for(R i = 2, lim, k, k1, k2, tmp; i <= x; i = lim + 1)
{
lim = min(x, x / (x / i)), k = x / i, dfs(k), dfs(k + 1);
k2 = x % i, k1 = i - k2, k2 %= 2, k1 %= 2;//有x % i堆k + 1,m - (x % i)堆k
tmp = (k1 * SG[k]) ^ (k2 * SG[k + 1]), vis[tmp] = 1;//对2取模，结果为1才计入贡献
if(i + 1 > lim) continue;//如果这一段就只有i这一个数，那就不能统计下面的
/*if(k & 1) vis[tmp ^ SG[k]] = true;//如果k是奇数
else vis[tmp ^ SG[k + 1]] = true;*/
++ i, k2 = x % i, k1 = i - k2, k2 %= 2, k1 %= 2;//有x % i堆k + 1,m - (x % i)堆k
tmp = (k1 * SG[k]) ^ (k2 * SG[k + 1]), vis[tmp] = 1;//懒得再分析了……直接再做一次吧
}
for(R i = 0; i <= 830; i ++)
if(!vis[i]) {SG[x] = i; break;}
}
void work()
{
T = read(), F = read();
while(T --)
{
n = read();int ans = 0;
for(R i = 1; i <= n; i ++)
{
int x = read();
dfs(x), ans ^= SG[x];
}
printf("%d ", ans != 0);
}
printf("
");
}
int main()
{
// freopen("in.in", "r", stdin);
work();
// fclose(stdin);
return 0;
}