Rinne Loves Xor

链接：https://ac.nowcoder.com/acm/contest/5505/B
来源：牛客网

时间限制：C/C++ 2秒，其他语言4秒
空间限制：C/C++ 262144K，其他语言524288K
64bit IO Format: %lld

题目描述

输入描述:
第一行一个整数 N，表示数组 A 和 B 的长度。
第二行 N 个整数表示数组 A。
第三行 N 个整数表示数组 B。
输出描述:
输出一行 N 个整数，表示加密后的数组 C。
示例1
输入
复制

10
65605 70259 77306 43823 61443 98602 9261 7662 46394 83019
81393 5966 61479 24259 92528 96132 35859 47981 11702 71736

输出
复制

15796 166270 623824 1132402 1650729 2445262 3256941 4150718 5106184 6353038

备注:
N≤10^5^, ai≤10^9^

题解：

本人也没做出来，看了其他题解，学到两个方法

方法一

参考题解
一下为个人结合题解的理解
暴力做O（n^2^）肯定超时

题目已经发式子给我们了，我们可以看出整个求解其实就是一个递推过程。由已知推位置，之前推出的后面也不会再修改。
异或：相同为0，不同为非0
最麻烦的就是后面这个部分
这个累加式子我们可以拆开

既然是异或，我们就用二进制来考虑，a与b异或，我们也可以把a与b都分成二进制，题目给的a的范围小于1e9,也就是a二进制最多为32位，所以这样完全ok
两个数位不同为1，如果当前数字二进制是1，前面这个数的这个位置的数如果是0，就可以贡献出1；反之也是。如果两个相同，则无法贡献
我们用到一个sum数组
sum[i][0]

sum1[i][0] 表示前面的 a 数组中二进制第 i 位为0 的数目
sum1[i][1]sum1[i][1] 表示前面的 a 数组中二进制第 i 位为 1 的数目
sum2[i][0]sum2[i][0] 表示前面的 b 数组中二进制第 i 位为 0 的数目
sum2[i][1]sum2[i][1] 表示前面的b 数组中二进制第 i 位为 1 的数目
代码为题解里的代码

#include<bits/stdc++.h>
using namespace std;

const long long inf = 1e18;
const int N = 1e6 + 5;
const double eps = 1e-10;
const int mod = 1e9 + 7;
typedef long long ll;

ll a[N], b[N];
ll ans[N];
ll sum1[64][2], sum2[64][2];
ll qpow(ll a, ll b) {
  ll res = 1;
  while(b) {
    if(b & 1) {
      res = res * a % mod;
    }
    a = a * a % mod;
    b >>= 1;
  }
  return res;
}
int main() {
  int n;
  cin >> n;
  for(int i = 1; i <= n; i++) cin >> a[i];
  for(int i = 1; i <= n; i++) cin >> b[i];
  for(int i = 1; i <= n; i++) {
    ll p = ans[i - 1] + (a[i] ^ b[i]) % mod;
    for(int j = 0; j <= 32; j++) {
      if(a[i] & (1LL << j)) { // 该位为1
        p += qpow(2, j) * sum2[j][0] % mod;
      }
      else { // 该位为0
        p += qpow(2, j) * sum2[j][1] % mod;
      }
      //cout << j << ' ' << sum2[j][0] << ' ' << sum2[j][1] << "\n";
    }
    for(int j = 0; j <= 32; j++) {
      if(b[i] & (1LL << j)) { // 该位为1
        p += qpow(2, j) * sum1[j][0] % mod;
      }
      else { // 该位为0
        p += qpow(2, j) * sum1[j][1] % mod;
      }
    }
    ans[i] = p % mod;
    for(int j = 0; j <= 32; j++) {
      if(a[i] & (1LL << j)) {
        sum1[j][1]++;
      }
      else sum1[j][0]++;
    }
    for(int j = 0; j <= 32; j++) {
      if(b[i] & (1LL << j)) {
        sum2[j][1]++;
      }
      else sum2[j][0]++;
    }
  }
  for(int i = 1; i <= n; i++) {
    cout << ans[i] % mod << " \n"[i == n];
  }
  return 0;
}

方法二：

个人感觉和上一个方法处理思想其实差不多
也是分成二进制进行对应数位异或
式子：
Ci=Ci-1+ai xor b1+ai xor b2+.....ai xor bi +ai-1 xor bi +...a1 xor bi

如果当前位数j，之前出现过4次1，另外一组出现过3次0，那么后面计算这一位给答案贡献就会是（4 * 3）<< j

pa[j][0/1]和pb[j][0/1]分别是a和b的在第j位之前0/1的数量
有个式子为
c[i] += (pa[j][0] * pb[j][1] + pa[j][1] * pb[j][0]) << j;
括号里就是相对应数位的数进行异或，而后面的<<j就是把这个数位的二进制转化成对应的十进制加给c

#include <iostream>
using namespace std;
typedef long long ll;

const int MOD = 1e9 + 7;
const int maxn = 1e5 + 2;
ll a[maxn], b[maxn], c[maxn];
ll pa[37][2], pb[37][2];

int main() {
    int n; 
    cin>>n; 
    for (int i = 1; i <= n; i++) cin>>a[i];
    for (int i = 1; i <= n; i++) cin>>b[i];
    for (int i = 1; i <= n; i++)
        for (int j = 0; j <= 30; j++) {
            pa[j][(a[i] >> j) & 1]++;
            pb[j][(b[i] >> j) & 1]++;//
            c[i] += (pa[j][0] * pb[j][1] + pa[j][1] * pb[j][0]) << j;
            c[i] %= MOD;
        }
    for (int i = 1; i <= n; i++)
        printf("%lld ", c[i]);
    return 0;
}