NC275631 嘤嘤不想求异或
讲真牛客这次的直播录屏讲得挺烂的(暴论),板书烂,表达烂...
求 \(1\sim x\) 的异或和
当然,求异或和本质上是求每一位的二进制值。
前置知识:
- 和十进制一样,二进制下最左边是高位,最右边是低位;
- 异或和计算中,偶数个 \(1\) 结果为,反之为 1。
循环周期推导
接下来推导为什么异或和的循环周期为 \(4\):
先从最基本的 \(1\;xor\;2\;xor\;3\;xor\;4 = 0\) 开始,
001 (1)
010 (2)
011 (3)
100 (4)
注意到前两位的 \(1\) 都是偶数,在排列组合中,两位的全排列需要 \(A_2^2=4\) 次完成,在这个周期内后面两位的异或结果为 \(0\),对后续周期没有影响。
再往下一个周期:
0100
0101 (1)
0110 (2)
0111 (3)
1000 (4)
将上个周期附加在下个周期的开头,由于前两位都是 \(0\),所以对异或结果没有影响。
也就是说,在 \(T=4\) 的情况下,每 4 次前 \(n-1\) 位的 1 的个数为偶数,则此时异或和等于该周期的最后一个数,即:
\[(x-3)\;xor\;(x-2)\;xor\;(x-1)\;xor\;x= x
\]
由右端点推出异或和
根据上面的规律,可以继续推导最后一个周期中的四个数与最终异或和的关系:
- 显然结果为 1
- \(x+1\),第一位结果为 1,等价于当前数再加 1
- \(0\),此时各位 \(1\) 都是偶数个
- 在 (3) 的情况下多写了一位,最终异或和就是当前数本身。
求 \(l\sim r\) 的异或和
已经知道异或和的值反映的是当前位上 \(1\) 的奇偶个数,又知道以下规律:
- 奇+奇=偶
- 奇+偶=奇
- 偶+偶=偶
也就是 \([1,l-1]_1+[l,r]_1=[1,r]_1\),根据已知规律可求的 \([1,l-1],[1,r]\) 即可唯一对应到 \([l,r]\) 的奇偶数,进而求出该位的异或和值。
不难发现,令奇数为 \(1\),偶数为 \(0\),\([l,r]_1=[1,l-1]_1\;xor\;[1,r]_1\)。