Rinne Loves Xor

题解：

　　看到二进制异或就可以想一下是否可以按位处理。我们可以通过计算二进制中每一位对答案贡献来解这个题。我们考虑异或运算会造成贡献的唯一可能就是当前位上的二进制数字不相同，那么对于每一位，贡献就是 A 第 j 位出现 1 的次数 × B 第 j 位出现 0 的次数 + B 第 j 位出现 1 的次数 ×A 第 j 位出现 0 的次数。 （乘法原理）最后按照这一位对总答案的贡献统计一下就可以了。

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<algorithm>
 5 using namespace std;
 6 typedef long long ll;
 7 const int maxn=1e5+10;
 8 const ll mod=1e9+7;
 9 ll x[32][2],y[32][2];//x[i][0]表示的是a[i]数组中第i位是0的个数 x[i][1]表示的是a[i]数组中第i位是1的个数 y数组同理 
10 ll a[maxn],b[maxn];
11 ll ans[maxn];
12 int n;
13 int main()
14 {
15     cin>>n;
16     for(int i=1;i<=n;i++)
17         scanf("%lld",&a[i]);
18     for(int i=1;i<=n;i++)
19         scanf("%lld",&b[i]);
20     for(int i=1;i<=n;i++)
21     {
22         ans[i]=ans[i-1]+(a[i]^b[i]);
23         ans[i]%=mod;
24         for(int j=0;j<32;j++)
25         {
26             ans[i]+=(x[j][!(b[i]>>j&1)]+y[j][!(a[i]>>j&1)])<<j;//因为只有两个数的某一位不同时会对结果有所贡献，所以遍历每一位，所以对于a[i]的第j位，需要寻找b[i]的第j位和a[i]第j位不相同的才可以，对于b[i]也一样。
27             ans[i]%=mod;
28             x[j][a[i]>>j&1]++;
29             y[j][b[i]>>j&1]++;
30         }
31         printf("%lld ",ans[i]);
32     }
33 }