給定一個(gè)長(zhǎng)度為 n n n 的數(shù)組 a 1 , a 2 , . . . , a n a_1,a_2,...,a_n a1?,a2?,...,an?。 請(qǐng)你求出下面式子的模 1 e 9 + 7 1e9+7 1e9+7的值。
∑ i = 1 n ? 1 ∑ j = i + 1 n ( a i ? X O R ? a j ) \sum_{i=1}^{n-1}{\sum_{j=i+1}^{n}{(a_i\ XOR\ a_j)}} ∑i=1n?1?∑j=i+1n?(ai??XOR?aj?)
輸入格式
第一行一個(gè)數(shù)字 n n n。
接下來(lái)一行 n n n 個(gè)整數(shù) a 1 , a 2 , … , a n a_1,a_2,…,a_n a1?,a2?,…,an?。
輸出格式
一行一個(gè)整數(shù)表示答案。
樣例輸入
3
1 2 3
樣例輸出
6
數(shù)據(jù)規(guī)模
所有數(shù)據(jù)保證 2 ≤ n ≤ 300000 , 0 ≤ a i < 2 60 2≤n≤300000,0≤a_i<2^{60} 2≤n≤300000,0≤ai?<260。
解題思路
依照題意，我們只能直接跑二重循環(huán)（因?yàn)?span id="n5n3t3z" class="katex--inline"> a i a_i ai?和 a j a_j aj?的組合不會(huì)重復(fù)，也就是說(shuō)沒(méi)有子結(jié)構(gòu)的概念），這肯定會(huì) T L E TLE TLE。
那么我們考慮異或操作的性質(zhì)：
異或操作是位操作，無(wú)視整個(gè)位串的意義，只能看到單個(gè)位。——條件（1）
然后重新審視 ∑ i = 1 n ? 1 ∑ j = i + 1 n ( a i ? X O R ? a j ) \sum_{i=1}^{n-1}{\sum_{j=i+1}^{n}{(a_i\ XOR\ a_j)}} ∑i=1n?1?∑j=i+1n?(ai??XOR?aj?)。
這個(gè)式子就是對(duì)任意兩個(gè)元素進(jìn)行異或操作然后做和，也就是說(shuō)嘗試了所有的組合（ C n 2 C_n^2 Cn2?）。——條件（2）
再來(lái)看一下異或操作的性質(zhì)：同則為假，不同為真。——條件（3）
如何利用三個(gè)條件優(yōu)化算法？這里通過(guò)一個(gè)簡(jiǎn)單的例子來(lái)理解：
有位串 10000111 1000 0111 10000111，我們對(duì)任意兩個(gè)位進(jìn)行異或操作，然后做和。很容易發(fā)現(xiàn)，其和為 4 ? 4 = 16 4*4=16 4?4=16。就是 1 1 1的數(shù)量乘上 0 0 0的數(shù)量。
然后我們回去看一眼題中的例子：
1 2 3
1 1 0 1 -> 2 * 1 = 2
2 0 1 1 -> 2 * 2 = 4
4 0 0 0 -> 0 * 4 = 0
比起之前那個(gè)簡(jiǎn)單的例子，也就是多了個(gè)權(quán)重，僅此而已。
接下來(lái)簡(jiǎn)單說(shuō)一下代碼如何實(shí)現(xiàn)：
我們維護(hù)每一個(gè)位上 1 1 1（也可以是 0 0 0）出現(xiàn)的次數(shù)；
然后遍歷每一個(gè)位，累計(jì)： 0 0 0的數(shù)量 ? 1 *1 ?1的數(shù)量 ? * ?權(quán)重。文章來(lái)源：http://www.zghlxwxcb.cn/news/detail-429690.html
AC代碼如下：文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-429690.html
#include <iostream>
using namespace std;
const int max_len = 60;
const long long max_a = (1LL << 60LL) - 1LL;
const int max_n = 300000;
const long long mod_num = 1e9 + 7;
long long sum[max_len];
inline void read() {
long long x, idx = 0;
cin >> x;
while (x) {
sum[idx++] += x & 1;
x >>= 1;
}
}
int main() {
int n;
cin >> n;
for (int i = 0; i < n; i++) read();
long long ans = 0;
for (int i = 0; i < max_len; i++) {
long long power = (1LL << (long long)(i)) % mod_num;
long long comb = sum[i] * (n - sum[i]) % mod_num;
ans = (ans + (power * comb) % mod_num) % mod_num;
}
cout << ans << endl;
return 0;
}
到了這里，關(guān)于[Daimayuan] 異或和（C++，異或，數(shù)學(xué)）的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
