Rinne Loves Xor

题意：

分析：

如果直接暴力算的话，复杂度：(O(N^2))，肯定不行。
一开始以为要用什么多项式的相关算法，看了别人的思路才发现可以从二进制位的角度考虑，算每个位的贡献是多少。
对于 (a[i])，它会和 (b[1] o b[i-1]) 依次异或，那么单独考虑每一位。对于第 (k) 位，当 (a[i]) 的第 (k) 位为 (1) 时，当有一个 (b) 的 (k) 位为 (0)，就会对答案贡献 (2^k)。在递推的时候计数即可。

代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod=1e9+7;
const int N=1e5+5;
int a[N],b[N],A[40][2],B[40][2];
ll c[N];
int main()
{
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);
    for(int i=1;i<=n;i++)
        scanf("%d",&b[i]);
    c[0]=0;
    for(int i=1;i<=n;i++)
    {
        c[i]=c[i-1]+(a[i]^b[i])%mod;
        for(int j=0;j<=30;j++)
        {
            int t=(a[i]>>j)&1;
            c[i]=(c[i]+1LL*B[j][1-t]*(1<<j)%mod)%mod;
            t=(b[i]>>j)&1;
            c[i]=(c[i]+1LL*A[j][1-t]*(1<<j)%mod)%mod;
            A[j][(a[i]>>j)&1]++;
            B[j][(b[i]>>j)&1]++;
        }
    }
    for(int i=1;i<=n;i++)
        printf("%lld%c",c[i]%mod,i==n?'
':' ');
    return 0;
}