分析
首先发现这是个 Multi-SG 游戏，那么可以考虑使用 SG 函数。
先考虑怎么暴力求 $SG(x)$ 。
大力枚举分成的堆数。如果将 $x$ 分成了 $i$ 堆，那么这 $i$ 堆中有 $x\bmod i$ 堆 $\left\lceil\frac{x}{i}\right\rceil$，有 $i-x\bmod i$ 堆 $\left\lfloor\frac{x}{i}\right\rfloor$ 。
于是只需要计算出所有后继游戏的 SG 函数（即后继游戏中所有状态 SG 函数的异或和），然后求 $\operatorname{mex}$ 即可得到 $SG(x)$。
因为要计算的是异或和，而 $a \operatorname{xor} a = 0$，于是只要根据 $x \bmod i$ 和 $i - x \bmod i$ 的奇偶性讨论一下就行了。
发现 $\left\lfloor\frac{x}{i}\right\rfloor$ 最多只有 $2\sqrt{n}$ 个取值，于是可以数论分块来枚举 $\left\lfloor\frac{x}{i}\right\rfloor$ 。
然后因为 $SG(\left\lceil\frac{x}{i}\right\rceil)$ 和 $SG(\left\lfloor\frac{x}{i}\right\rfloor)$ 是否产生贡献只和 $x \bmod i$ 和 $i-x \bmod i$ 的奇偶性有关，于是只要算 $i$ 与 $i+1$ 的情况，因为分为 $\geq i+2$ 堆时的 SG 函数一定和 $SG(i)$ 与 $SG(i+1)$ 中的一个相等。
代码
//It is made by M_sea
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define re register
using namespace std;
inline int read() {
int X=0,w=1; char c=getchar();
while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
return X*w;
}
int sg[100010],vis[100010];
int T,F;
inline int SG(int x) {
if (x<F) return 0;
if (sg[x]!=-1) return sg[x];
for (re int l=2,r;l<=x;l=r+1) {
r=x/(x/l);
for (re int j=l;j<=min(l+1,r);++j) {
int a=x%j,b=x/j+1,c=j-x%j,d=x/j,s=0;
if (a&1) s^=SG(b);
if (c&1) s^=SG(d);
vis[s]=x;
}
}
for (re int i=0;;++i)
if (vis[i]!=x) return sg[x]=i;
}
int main() {
memset(sg,-1,sizeof(sg));
T=read(),F=read();
while (T--) {
int n=read(),ans=0;
for (re int i=1;i<=n;++i) ans^=SG(read());
printf("%d ",(bool)ans);
}
putchar('\n');
return 0;
}
5 条评论
M-sea做题怎么这么快啊QAQ
哪里快了qwq
您比我快多了qwq
怎么这么假啊qwq
%%%
%%%%%