Queue

myzzym · 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)}。