Rinne Loves Xor

NC22601. Rinne Loves Xor

描述

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

$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_i$ 模

的结果即可。

输入描述

第一行一个整数 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

上次编辑到这里，代码来自缓存点击恢复默认模板

C++14(g++5.4) 解法, 执行用时: 109ms, 内存消耗: 2980K, 提交时间: 2019-11-28 10:46:09

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

long long k,A[100005],B[100005],a[32][2],b[32][2];
int main()
{
	int i,j,N,M=1e9+7;
	scanf("%d",&N);
	for(i=1;i<=N;i++)scanf("%lld",&A[i]);
	for(i=1;i<=N;i++)scanf("%lld",&B[i]);
	for(i=1;i<=N;i++)
	{
		for(k=j=0;j<31;j++)
		{
			a[j][(A[i]>>j)&1]++;
			b[j][(B[i]>>j)&1]++;
			k+=(a[j][0]*b[j][1]+a[j][1]*b[j][0])<<j,k%=M;
		}
		printf("%d ",k);
	}
	printf("\n");
    return 0;
}

C++11(clang++ 3.9) 解法, 执行用时: 102ms, 内存消耗: 2936K, 提交时间: 2020-02-27 12:36:18

#include<bits/stdc++.h>
using namespace std;
long long k,A[100005],B[100005],a[32][2],b[32][2];
int main()
{
	int i,j,N,M=1e9+7;
	scanf("%d",&N);
	for(i=1;i<=N;i++) scanf("%lld",&A[i]);
	for(i=1;i<=N;i++) scanf("%lld",&B[i]);
	for(i=1;i<=N;i++)
	{
		for(k=j=0;j<31;j++)
		{
			a[j][(A[i]>>j)&1]++;
			b[j][(B[i]>>j)&1]++;
			k+=(a[j][0]*b[j][1]+a[j][1]*b[j][0])<<j,k%=M;
		}
		printf("%d ",k);
	}
	printf("\n");
	return 0;
}