自动搬运

查看原文

来自洛谷，原作者为

	Mophie 祈祷着你今后的人生，永远都会有幸福的魔法相伴。

搬运于2025-08-24 22:22:39，当前版本为作者最后更新于2021-04-28 09:50:35，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

初学 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$

$2x+3$ 的前缀和就为 $0$。

然后直接做就好了。

代码如下（貌似还是最优解？）

//红太阳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;
}