自动搬运

查看原文

来自洛谷，原作者为

	myzzym 每天都在倒退，是你想看到的吗

搬运于2025-08-24 22:57:40，当前版本为作者最后更新于2024-04-11 18:54:49，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

（稍微打下表就可以得到答案的规律题）

结论：当 $n\bmod 4=1$ 时答案为 $n$。

当 $n\bmod 4=2$ 时答案为 $n-2$。

当 $n\bmod 4=3$ 时答案为 $3$。

当 $n\bmod 4=0$ 时答案为 $0$。

我们可以通过暴力求出答案序列为 $1,0,3,0,5,4,3,0,\ldots,x,x-2,3,0$，很容易找到规律，下面讲一下为什么会出现这种情况。

我们发现第 $4r$ 个人的值都是 $0$，那有没有可能不为 $0$ 呢？假设我们已经求得第 $4r$ 个人的值为 $0$，则第 $4r+1$ 个人的值也就为 $4r+1$，而第 $4r+2$ 的第二位以后的值与 $4r+1$ 一致，所以只会把前两位清零，所以值为 $4r$，第 $4r+3$ 个人的第二位以后的值也是一致的，异或后第二位以后的值变成 $0$，而第 $4r+2$ 个人的数前两位的值是 $0$，所以异或后值为 $3$，第 $4r+4$ 个人前两位是 $0$,所以 $4r$ 的值一定为 $0$，相应的 $4r+1,4r+2,4r+3$ 的值也如上文所说。

例子：第 $4$ 到第 $8$ 个人数的变化：$0_{(2)}\to101_{(2)}\to100_{(2)}\to11_{(2)}\to0_{(2)}$。