題目連結：
題目大意：
給定一正整數 N （N ≦ 10 ^ 5），代表一集合 A 的元素個數。接著的一列有 N 個整數 Ai （N ＞ i ≧ 0），代表集合 A 之中的元素。
求先將 A 的所有子集合各自的元素作 XOR 運算後，再全部加總的結果為何？例如，A ＝ { X1, X2, X3 }，即是求 0 ＋ X1 ＋ X2 ＋ X3 ＋ （ X1 ⊕ X2 ）＋（ X1 ⊕ X3 ）＋（ X2 ⊕ X3 ）＋（ X1 ⊕ X2 ⊕ X3 ）。
由於結果可能很大，因此將結果取 1000000007 的餘數再輸出。
範例輸入：
3
1 2 3
4
1 2 4 8
5
1 2 3 5 100
範例輸出：
12
120
1648
解題思維：
觀察以下以兩個二進位位元表示的數字之範例：
00
01
11
其子集合各自將元素 XOR 後的結果有以下八個（2 ^ 3）：
00
00
01
11
01
11
10
10
左邊、右邊的位元是 1 的數字各自有 4 個。
而另一範例：
00
00
01
子集合 XOR 結果也有八種：
00
00
00
01
00
01
01
01
這次只有右邊的位元有 4 個數字在其位置為 1 。
多觀察幾個範例，可以看到當有一個位置的位元在某數中為 1 時，其在子集合中為 1 的數量必為 2 ^ （N － 1） 個。例如範例輸入的 1 、 2 、 4 、 8 ，化為二進位後為
0001
0010
0100
1000
則各個位置為在子集合 XOR 後為 1 的皆是 2 ^ 3 ＝ 8 個。也就是說，所求即為
8 ×（2 ^ 3 ＋ 2 ^ 2 ＋ 2 ＋ 1） ＝ 120
而 1 、 2 、 3 、 5 、 100 轉為二進位後為
0000001
0000010
0000011
0000101
1100100
因為有兩個位置沒有在任何數字是 1 的情況（2 ^ 3 、 2 ^ 4 那兩位），因此結果為
16 × （2 ^ 6 ＋ 2 ^ 5 ＋ 2 ^ 2 ＋ 2 ＋ 1）＝ 1648
所以，只要有數字在某位元（2 ^ k）為 1 ，則該位元會為結果貢獻 2 ^ k × 2 ^ （N － 1）。
再加上餘數的性質：先運算再取餘 與 先取餘再運算，兩者的結果仍然同餘。因此我們可以將結果保持在 int （2 ^ 32）以內，而不需大數運算。
此次分享到此為止，如有任何更加簡潔的想法或是有說明不清楚之地方，也煩請各位大大撥冗討論。
