一个有意思的数学结论

今天在整理这道题
链接: 子数组异或和
发现了一个比较有意思的数学结论，在这里分享一下。

给一个数组，[$a_1$,$a_2$,…,$a_n$]，讲这个数组分成两个区间，使得左半边的异或和==右半边的异或和，即 $x=y$。
那么将这个区间重新划分，是否能得到$x^{\prime }=y^{\prime }$？
结论一：能得到$x^{\prime }=y^{\prime }$
证明：
异或和，就是将这些数字连续异或所得的数字，x=$a_1\oplus a_2\oplus ...a_x$。
结果的二进制位上的每一位究竟是 1 or 0 是根据这组数字的二进制在这以为上的 1 的奇偶情况，如果1的个数是奇数，那么这一位是1，否则是0
那么举一个简单的例子：
$a[4]=$[1,1,1,1]

1. [1,1 | 1,1] $x=0,y=0$,
2. [1 | 1,1,1] $x^{\prime }=1,y^{\prime }=1$,

不难发现：两个区间异或和相同，所以两边数字的二进制的各个位上的1的奇偶性是一致的，划分区间时中间指针的移动，两个区间的奇偶性始终保持一直。
结论二：[i,i+1,…,j]的异或和 = s[j]^s[i-1]。
证明：
s[i]表示前i个字母的异或前缀和,求[i ~ j]这一段的异或和:$s_j\oplus s_{i-1}$
因为$s_j$是$a_1\oplus a_2\oplus ...\oplus a_{i-1}\oplus a_i\oplus ...\oplus a_j$
$s_{i-1}是a_1\oplus a_2\oplus ...\oplus a_{i-1}$
所以$s_j\oplus s_{i-1}==a_i\oplus ...\oplus a_j$,即是[i ~ j]这一段的异或和。