Rinne Loves Xor

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

题目描述

Rinne 最近学习了位运算相关的知识，她想运用自己学习的知识发明一个加密算法。
首先她有一个源数组 A，还有一个密钥数组 B，现在她想生成加密后的数组 C。
她发明的方法是：当计算CiCi的时候，首先将 CiCi 赋值为Ci−1Ci−1，然后加上 AiAi 分别与每一个满足 j < i 的 BjBj 异或后的和，然后加上 BiBi 分别与每一个满足 j < i 的 AjAj 异或后的和，最后加上 AiAi 与 BiBi 的异或和。
形式化的讲，关于 CiCi 的递推式为以下式子：

现在她想用程序来实现这个过程，你能帮帮她吗？由于输出可能太大，你只需要输出每个 Ci模 109+7的结果即可。

输入描述:

第一行一个整数 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≤105,ai≤109

大致思路

1. 由Ci的式子可知，如果能以常数复杂度的时间来求出，那么这个题目就可以过。

2. 这个式子可以看成一个数和一串数字的异或和。

3. 考虑两个二进制数字的异或和，考虑第i位，只有当一个数字的第i位为0/1并且另一个数字的第i位为1/0时，这两个数字的异或和的二进制表示的第i位为1。

4. 那么考虑一个数字和一串数字的异或和，考虑第i位，当一个数字的第i位为0/1时，只有一串数字中该位为1/0的数字可以对答案产生贡献(1<<j)。

5. 维护两个数字的二进制表示下0/1个数的前缀和，就可以在常数复杂度下求出式子。

Code

#include <bits/stdc++.h>
#define ll long long
const ll mod = 1e9 + 7;
using namespace std;
int a[100005][32], b[100005][32];
ll sa[32][2], sb[32][2];
ll ans[100005];
int main()
{
	int n, t;
	scanf("%d", &n);
	for (int i = 1; i <= n; i++)
	{
		scanf("%d", &t);
		for (int j = 0; j < 32; j++)
		{
			if (t&(1 << j))
				a[i][j] = 1;
		}
	}
	for (int i = 1; i <= n; i++)
	{
		scanf("%d", &t);
		for (int j = 0; j < 32; j++)
		{
			if (t&(1 << j))
				b[i][j] = 1;
		}
	}
	for (int i = 1; i <= n; i++)
	{
		ans[i] = ans[i - 1];
		for (int j = 0; j < 32; j++)
		{
			if (a[i][j] != b[i][j])
				ans[i] += 1 << j;
			ans[i] %= mod;
			ans[i] += sb[j][!a[i][j]] << j;
			ans[i] %= mod;
			ans[i] += sa[j][!b[i][j]] << j;
			ans[i] %= mod;
			sa[j][a[i][j]]++;
			sb[j][b[i][j]]++;
		}
		printf("%lld%c", ans[i], i != n ? ' ' : '\n');
	}
}