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

题目描述

Rinne 最近学习了位运算相关的知识,她想运用自己学习的知识发明一个加密算法。
首先她有一个源数组 A,还有一个密钥数组 B,现在她想生成加密后的数组 C。
她发明的方法是:当计算$$C_i$$的时候,首先将 $$C_i$$赋值为$$C_{i-1}$$,然后加上$$ A_i$$ 分别与每一个满足 $$j \lt i$$ 的 $$B_j$$ 异或后的和,然后加上 $$B_i$$ 分别与每一个满足 $$j \lt i$$ 的 $$A_j$$ 异或后的和,最后加上 $$A_i$$ 与 $$B_i$$ 的异或和。
形式化的讲,关于 $$C_i$$ 的递推式为以下式子:

$$
\begin{aligned}
&C_0 = 0
\&C_i = C_{i-1} + A_i xor B_i + (\sum_{j=1}^{i-1} (A_i xor B_j + A_j xor B_i))C
\end{aligned}
$$
现在她想用程序来实现这个过程,你能帮帮她吗?由于输出可能太大,你只需要输出每个 $$C_i$$ 模 $$10^9+7$$ 的结果即可。

输入描述:

第一行一个整数 N,表示数组 A 和 B 的长度。
第二行 N 个整数表示数组 A。
第三行 N 个整数表示数组 B。

输出描述:

输出一行 N 个整数,表示加密后的数组 C。

示例1

输入

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

输出

1
15796 166270 623824 1132402 1650729 2445262 3256941 4150718 5106184 6353038

备注:
$$
N \leq 10^5 ,a_i \leq 10^9N≤10
$$

思路

我们不难发现,数字的每一个位是独立的,他们对答案的影响互不干扰,于是我们就可以吧数字拆开,一位一位的考虑,
当我们只考虑一位的时候,答案就只和1的个数有关了。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include<bits/stdc++.h>
using namespace std;

void sum01(int*a,int*b,int*c,int n,int mod){
long long sa=0,sb=0;
for(int i=0;i<n;i++){
sa+=a[i];
sb+=b[i];
c[i]=(sa*(i+1-sb)+sb*(i+1-sa))%mod;
}
}
void sum(int*a,int*b,int*c,int n,int mod){
vector<int> a01(n),b01(n),c01(n);
for(int mask=1;mask<=1e9;mask<<=1){
for(int i=0;i<n;i++){
a01[i] = (mask&a[i]) ? 1:0;
b01[i] = (mask&b[i]) ? 1:0;
}
sum01(a01.data(),b01.data(),c01.data(),n,mod);
for(int i=0;i<n;i++) c[i] = (c[i]+1ll*c01[i]*mask)%mod;
}
}

int main(){
int n;
cin>>n;
vector<int> a(n),b(n),c(n);
for(int i=0;i<n;i++) cin>>a[i];
for(int i=0;i<n;i++) cin>>b[i];
sum(a.data(),b.data(),c.data(),n,1e9+7);
for(int i=0;i<n;i++) cout<<c[i]<<" ";
cout<<endl;
}