异或运算的性质#

TIP

异或运算（$\oplus$）的本质是“不进位的二进制加法”。

1. 归零律与恒等律：$A \oplus A = 0$，$A \oplus 0 = A$。

   任何数字与自身异或都会“抵消”归零；任何数字与 $0$ 异或保持不变。这也是异或前缀和能够实现区间查询的根本原因。

2. 交换律与结合律：$A \oplus B = B \oplus A$，$A \oplus (B \oplus C) = (A \oplus B) \oplus C$。

   异或的顺序不重要。这意味着在一堆数字中，可以随意改变它们的异或顺序，结果不变。

3. 方程的同解性：如果 $A \oplus B = C$，那么必然有 $A \oplus C = B$ 且 $B \oplus C = A$。

   这个性质在解题时经常用于“已知目标求变量”。比如想找一个前缀和 $P[l]$ 使得 $P[r] \oplus P[l] = K$，可以直接转换为寻找 $P[l] = P[r] \oplus K$。

异或前缀和#

假设有一个任意数组 $A$，我们定义它的异或前缀和数组为 $S$，其中 $S[i] = A[1] \oplus A[2] \oplus \dots \oplus A[i]$，且 $S[0] = 0$。

我们可以 $O(1)$ 地求区间异或和。任意区间 $[L, R]$ 的异或和为 $S[R] \oplus S[L-1]$。

推导过程：

$S[R] = A[1] \dots \oplus A[L-1] \oplus A[L] \dots \oplus A[R]$

$S[L-1] = A[1] \dots \oplus A[L-1]$

两者相异或，根据异或的第一条性质，$A[1]$ 到 $A[L-1]$ 被全部抵消，只剩下 $A[L] \dots \oplus A[R]$。

允许为空的隔板法#

NOTE

把 $n$ 个完全相同的球，放进 $m$ 个不同的盒子里，允许有的盒子为空，一共有多少种放法？

答案为：$\binom{n + m - 1}{m - 1}$，由于组合数的对称性，也等于$\binom{n+m-1}{n}$。

如果不允许为空（每个盒子至少 1 个），那非常简单：$n$ 个球排成一排，中间有 $n-1$ 个空隙。要把它们分成 $m$ 份，只需要从这 $n-1$ 个空隙里挑出 $m-1$ 个位置，插入隔板即可。方案数直接就是 $\binom{n-1}{m-1}$。

但现在允许为空，传统的插板法就失效了，因为你可以把两块隔板插在同一个空隙里，或者插在最边缘。为了解决这个问题，我们使用一种“先借后还”的思想：