異或和之和

題目來源

第十四屆藍橋杯大賽軟件賽省賽C/C++ 大學 A 組

原題鏈接

藍橋杯 異或和之和 https://www.lanqiao.cn/problems/3507/learning/

問題描述

問題分析

要點1：異或運算

概念

異或（Exclusive OR，簡稱 XOR）是一種數學運算符，常用于邏輯運算與計算機中的位運算。當且僅當兩個輸入值不同時，異或運算輸出為真（1），否則輸出為假（0），即“同為 0，異為 1”。異或運算可以通過數學符號“⊕”表示， 具有交換律、結合律、恒等律等性質。
在編程語言中通常為 p^q。

通俗運算

一位運算：
1 ⊕ 1 = 0，0 ⊕ 0 = 0；
1 ⊕ 0 = 1，0 ⊕ 1 = 1；
1 ⊕ 1 ⊕ 1 =1，1 ⊕ 1 ⊕ 0 =0；
也就是說，奇數個1則結果為1，偶數個1則結果為0.

多位運算：
例如，計算 $5\oplus 3$， 需要先轉換成二進制，再對每一位取異或，輸出二進制后再轉換為十進制。
5 = 101 ，3 = 011，6=110
$101\oplus 011=110$
$5\oplus 3=6$。

要點2：異或前綴和

遞推關系

$s[i]$ 表示從第一個值到當前第i個值的所有異或和，
即$s[i]$ = a[1] ^ a[2] ^ a[3] ··· a[i-1] ^ a[i] 的異或和，
則 $s[i?1]$ = a[1] ^ a[2] ^ a[3] ··· a[i-1] 的異或和，
易得，s[i] = s[i-1] ^ a[i] 。

前綴和反推異或和

s [