鏈接：

來源：牛客網

時間限制：C/C++ 2秒，其他語言4秒 空間限制：C/C++ 262144K，其他語言524288K 64bit IO Format: %lld

題目描述

輸入描述:
第一行一個整數 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≤10⁵, ai≤10⁹

題解：

本人也沒做出來，看了其他題解，學到兩個方法

方法一

參考題解
一下為個人結合題解的理解
暴力做O（n²）肯定超時

題目已經發式子給我們了，我們可以看出整個求解其實就是一個遞推過程。由已知推位置，之前推出的后面也不會再修改。
異或：相同為0，不同為非0
最麻煩的就是后面這個部分
這個累加式子我們可以拆開

既然是異或，我們就用二進制來考慮，a與b異或，我們也可以把a與b都分成二進制，題目給的a的范圍小于1e9,也就是a二進制最多為32位，所以這樣完全ok
兩個數位不同為1，如果當前數字二進制是1，前面這個數的這個位置的數如果是0，就可以貢獻出1；反之也是。如果兩個相同，則無法貢獻
我們用到一個sum數組
sum[i][0]

sum1[i][0] 表示前面的 a 數組中二進制第 i 位為0 的數目
sum1[i][1]sum1[i][1] 表示前面的 a 數組中二進制第 i 位為 1 的數目
sum2[i][0]sum2[i][0] 表示前面的 b 數組中二進制第 i 位為 0 的數目
sum2[i][1]sum2[i][1] 表示前面的b 數組中二進制第 i 位為 1 的數目

#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)) { // 該位為1p += qpow(2, j) * sum2[j][0] % mod;}else { // 該位為0p += 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)) { // 該位為1p += qpow(2, j) * sum1[j][0] % mod;}else { // 該位為0p += 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; }

方法二：

個人感覺和上一個方法處理思想其實差不多
也是分成二進制進行對應數位異或
式子：
C_i=C_i-1+ai xor b1+ai xor b2+…ai xor bi +ai-1 xor bi +…a1 xor bi

如果當前位數j，之前出現過4次1，另外一組出現過3次0，那么后面計算這一位給答案貢獻就會是（4 * 3）<< j

pa[j][0/1]和pb[j][0/1]分別是a和b的在第j位之前0/1的數量
有個式子為
c[i] += (pa[j][0] * pb[j][1] + pa[j][1] * pb[j][0]) << j;
括號里就是相對應數位的數進行異或，而后面的<<j就是把這個數位的二進制轉化成對應的十進制加給c

#include <iostream> using namespace std; typedef long long ll;const int MOD = 1e9 + 7; const int maxn = 1e5 + 2; ll a[maxn], b[maxn], c[maxn]; ll pa[37][2], pb[37][2];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++)for (int j = 0; j <= 30; j++) {pa[j][(a[i] >> j) & 1]++;pb[j][(b[i] >> j) & 1]++;//c[i] += (pa[j][0] * pb[j][1] + pa[j][1] * pb[j][0]) << j;c[i] %= MOD;}for (int i = 1; i <= n; i++)printf("%lld ", c[i]);return 0; }

總結

以上是生活随笔為你收集整理的Rinne Loves Xor的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。