牛客算法周周练4 B Rinne Loves Xor

Solution

挺简单的一道题, 虽然带着异或的皮, 看起来很复杂, 但其实只要我们从二进制位考虑就不难了
因为题目所给的数据是 $a_i <= 1e9$
因此二进制位上最多也就 $32$ 位, $n <= 1e5$ , 我们考虑能否有 $O(32n)$ 的做法
观察递推式 $C_i = C_{i - 1} + a_i \ xor \ b_i + \sum\limits_{j = 1}^{i - 1} (a_i \ xor \ b_j + a_j + \ xor \ b_i)$
前面两个可以 $O(1)$ 完成不用管
重点是后面那个累加式子, 我们把它们拆开其实也就是

$\sum\limits_{j = 1}^{i - 1} (a_i \ xor \ b_j) = a_i \ xor \ b_1 + a_i \ xor \ b_2 + .... a_i \ xor \ b_{i - 1}$
$\sum\limits_{j = 1}^{i - 1} (b_i \ xor \ a_j) = b_i \ xor \ a_1 + b_i \ xor \ a_2 + .... b_i \ xor \ a_{i - 1}$

从贡献方面考虑, 异或只会留下和这个数二进制位上不同的那些位, 那么我们只需要统计二进制位的出现情况
然后对于当前数字, 如果二进制位是 $1$ , 那么前面该位为 $0$ 的数字就有贡献
反之，如果二进制位是 $0$ , 那么前面该位为 $1$ 的数字就有贡献
贡献为 $sum[i][0] / sum[i][1] * 2 ^ i$
令

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

扫一遍统计即可, 因为比较懒, 时间比较宽裕, 下面做法复杂度 $O(64nlogn)$

Code

/*
  autor: Kurisu
  2020年4月30日16:48:49
*/
#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;
}