NC275631 嘤嘤不想求异或

讲真牛客这次的直播录屏讲得挺烂的(暴论),板书烂,表达烂...

\(1\sim x\) 的异或和

当然,求异或和本质上是求每一位的二进制值。
前置知识:

  1. 和十进制一样,二进制下最左边是高位,最右边是低位;
  2. 异或和计算中,偶数个 \(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. 显然结果为 1
  2. \(x+1\),第一位结果为 1,等价于当前数再加 1
  3. \(0\),此时各位 \(1\) 都是偶数个
  4. 在 (3) 的情况下多写了一位,最终异或和就是当前数本身。

\(l\sim r\) 的异或和

已经知道异或和的值反映的是当前位上 \(1\) 的奇偶个数,又知道以下规律:

  1. 奇+奇=偶
  2. 奇+偶=奇
  3. 偶+偶=偶

也就是 \([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\)

热门相关:寒门状元   神医娘亲之腹黑小萌宝   侯门弃女:妖孽丞相赖上门   笑傲在明天粤语   惊悚乐园