description:
给出数组A和B 求
solution:
首先我们根据乘法原理 可以把式子转变成 可以模拟一下题目的公式发现展开来这两的展开项是一样的,我们知道异或只有对应的位不同才对答案有贡献,所以我们将每个数拆分成每一位,按照位来处理
结果分别是Ai的0位 * Bi的1位 + Ai的1位 * Bi的0位 最后要左移对应的位数还原答案即可
code:
#include <bits/stdc++.h> using namespace std; #define LL long long const int N = 1e5 + 4; const LL mod = 1e9 + 7; LL a[N],b[N],c[N]; LL x[35][2],y[35][2]; int main(){ ios::sync_with_stdio(0); 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 j = 0;j <= 30;j ++){ x[j][(a[i] >> j) & 1] ++ ; y[j][(b[i] >> j) & 1] ++ ; c[i] += (x[j][0] * y[j][1] + x[j][1] * y[j][0]) << j; c[i] %= mod; } } for(int i = 1;i <= n;i ++){ cout << c[i] << ' '; } return 0; }