常用的性质们
SkyWave
·
·
个人记录
异或
设 x \oplus y 为 x 与 y 按位异或的结果，x \oplus y \oplus z 为 x 与 y 的按位异或的结果，与 z 进行异或的结果，即 (x \oplus y) \oplus z。
前缀异或和
设：
S(n) = 1 \oplus 2 \oplus 3 \oplus \cdots \oplus n
则有：
S(n) =
\begin{cases}
n & \text{if } n \bmod 4 = 0 \\
1 & \text{if } n \bmod 4 = 1 \\
n+1 & \text{if } n \bmod 4 = 2 \\
0 & \text{if } n \bmod 4 = 3 \\
\end{cases}
异或与矩阵
设 a 为一个 n 行 m 列矩阵，矩阵内每个元素为非负整数。设 a_{i_j} 为 a 第 i 行与第 j 列的交点的元素的值。
对于 i \in [n]，设 r_i 为 \bigoplus_{j=1}^{m} a_{i_j}，对于 i \in [m]，设 c_i 为 \bigoplus_{j=1}^{m} a_{j_i}，则有：
\left( \bigoplus_{i=1}^{n} r_i \right) = \left( \bigoplus_{i=1}^{m} c_i \right)