P6639 「JYLOI Round 1」让 题解
Mophie
·
·
题解
初学 SG 函数，按标签搜题搜到这题就做掉了qwq
首先每一堆的石子是相互独立的，那么我们只要求出每堆石子的 SG 函数即可。
打表观察一下 SG 函数的规律就可以发现，大概是 0-k_i 的循环。
那么现在考虑一下 0 每次出现的位置，显然就是恰好走不到上一个 0 的位置。
那么设上一个 0 的位置为 pos，石子总数为 R。设这个 0 的位置为 x
那么可以发现如果跳不到上一个 0 的话要满足条件 pos<x-(R-x) 也就是 2x>pos+R
所以下一个 x 的位置就是 pos+R+1 除 2 向上取整。然后就是前缀和处理的问题了。
首先有个比较显然的性质 2x \bigoplus 2x+1=1。因为前面位数全部相同就末位不同故异或值是 1。
那么 2x \bigoplus 2x+1 \bigoplus 2x+2 \bigoplus 2x+3=0，所以以每四个为周期。
然后就是 2x 的前缀和为 2x。
2x+1$ 的前缀和为 $2x \bigoplus 2x+1=1
2x+2$ 的前缀和为 $2x \bigoplus 2x+1 \bigoplus 2x+2=1 \bigoplus 2x+2 =2x+3
然后直接做就好了。
代码如下（貌似还是最优解？）
```cpp
//红太阳zhouakngyang txdy!
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
#include<bits/stdc++.h>
using namespace std;
#define int long long
inline int read()
{
int sum=0,nega=1;char ch=getchar();
while(ch>'9'||ch<'0'){if(ch=='-')nega=-1;ch=getchar();}
while(ch<='9'&&ch>='0')sum=sum*10+ch-'0',ch=getchar();
return sum*nega;
}
inline int val(int x)
{
if(x%4==1)return 1;
else if(x%4==2)return x^1;
else if(x%4==3)return 0;
else return x;
}
int taxi,p,n,ans,l,r,now=0;
char a[19];
inline int solve(int x,int k)
{
register int res=0,L=0,R=0,qwq;
while(L<=x)
{
qwq=k/2;R=L+qwq;
if(R>=x)
{
res=res^val(x-L);
break;
}
res=res^val(R-L);
L=R+1;k=p-L;
}
return res;
}
signed main()
{
taxi=read();
for(int ttt=1;ttt<=taxi;ttt++)
{
cin>>a;
if(a[0]=='c')p=read();
else
{
ans=0;
n=read();
for(int i=1;i<=n;i++)
{
l=read(),r=read();
ans=ans^solve(r,p);ans=ans^solve(l-1,p);
}
if(ans)putchar('1');
else putchar('0');
}
}
return 0;
}
```