e275: Xor and Parity

e275: Xor and Parity

題 意:

如 果 整 數 $x$ 在 二 進 制 下 有 奇 數 個 1，那 $x$ 的 $parity$ 為 1。反 之。
現 在 有 $n$ 個 非 負 整 數，請 問 有 多 少 數 對 $(i, j)$ 滿 足 $i < j$ 且 $a_i$ $xor$ $a_j$

solve:
假 設 有 三 非 負 整 數 $a$、$b$、$c$。令 $c$ = $a$ $xor$ $b$
$c$ 1 的 個 數 為 $a$ 1 的 個 數 + $b$ 1 的 個 數 - 2 * 相 同 的 位 元 個 數。

得 $a$ 與 $b$ 的 $parity$ 為 1 時，$c$ $parity$ 必 是 0。

而 $a$ 與 $b$ 的 $parity$ 為 0 時，同 上。

亦 $a$ 與 $b$ 的 $parity$ 不 同 時，$c$ $parity$ 為 1。

故 只 要 計 算 $parity$ 1 及 0 的 個 數，$C^n_2 - parity_0 \times parity_1$ 及 解。

code: