題干：
?

Rinne 最近學習了位運算相關的知識，她想運用自己學習的知識發明一個加密算法。
首先她有一個源數組 A，還有一個密鑰數組 B，現在她想生成加密后的數組 C。
她發明的方法是：當計算CiCi的時候，首先將 CiCi 賦值為Ci?1Ci?1，然后加上 AiAi 分別與每一個滿足 j < i 的 BjBj 異或后的和，然后加上 BiBi 分別與每一個滿足 j < i 的 AjAj 異或后的和，最后加上 AiAi 與 BiBi 的異或和。
形式化的講，關于 CiCi 的遞推式為以下式子：

C0=0C0=0

Ci=Ci?1+AixorBi+(∑i?1j=1(AixorBj+AjxorBi))Ci=Ci?1+AixorBi+(∑j=1i?1(AixorBj+AjxorBi))

現在她想用程序來實現這個過程，你能幫幫她嗎？由于輸出可能太大，你只需要輸出每個 CiCi 模 109+7109+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的數的個數，是0的數的個數，最后對于每一次查詢，直接調用這個前綴，然后做一次異或就行了。

AC代碼：

#include<cstdio> #include<iostream> #include<algorithm> #include<queue> #include<map> #include<vector> #include<set> #include<string> #include<cmath> #include<cstring> #define ll long long #define pb push_back #define pm make_pair #define fi first #define se second using namespace std; const int MAX = 2e5 + 5; const ll mod = 1e9+7; ll a[MAX],b[MAX],c[MAX]; ll A[33][2],B[33][2]; ll ans; int main() {int n;cin>>n;for(int i = 1; i<=n; i++) scanf("%lld",a+i);for(int i = 1; i<=n; i++) scanf("%lld",b+i);for(int i = 1; i<=n; i++) {ans = 0;ans = (c[i-1] + (a[i]^b[i]))%mod;for(int j = 0; j<33; j++) {ans += ((A[j][ !(b[i]>>j&1) ] + B[j][ !(a[i]>>j&1) ])<<j)%mod;A[j][a[i]>>j&1]++, B[j][b[i]>>j&1]++;}c[i] = ans%mod;}for(int i = 1; i<=n; i++) printf("%lld%c",c[i],i == n ? '\n' : ' ');return 0 ;}

?總結：

? 幾個小地方，以后尋找哪一位，還是用右移這種吧，，因為與運算完了之后就是非零即一，而不是非零即2^n。

?還有啊異或運算的優先級低于+運算，所以那個ans=的時候需要在 a[i]^b[i] 外面加括號。。

?

運用乘法原理也可以簡單求出答案，因為通過畫圖不難看出，Ci其實就是A數組和B數組所有 非同一數組 的元素都進行過一次異或操作

AC代碼2：

#include<cstdio> #include<iostream> #include<algorithm> #include<queue> #include<map> #include<vector> #include<set> #include<string> #include<cmath> #include<cstring> #define ll long long #define pb push_back #define pm make_pair #define fi first #define se second using namespace std; const int MAX = 2e5 + 5; const ll mod = 1e9+7; ll a[MAX],b[MAX],c[MAX]; ll A[33][2],B[33][2]; int main() {int n;cin>>n;for(int i = 1; i<=n; i++) scanf("%lld",a+i);for(int i = 1; i<=n; i++) scanf("%lld",b+i);for(int i = 1; i<=n; i++) {for(int j = 0; j<33; j++) {A[j][a[i]>>j&1]++, B[j][b[i]>>j&1]++;c[i] += ((A[j][0]*B[j][1]+A[j][1]*B[j][0])<<j)%mod;}}for(int i = 1; i<=n; i++) printf("%lld%c",c[i],i == n ? '\n' : ' ');return 0 ;}

寫這份代碼的時候傻了，，c[i]=了直接，應該是+=。。因為內層循環是要循環的啊、、又不是c[i]只算一遍。

創作挑戰賽新人創作獎勵來咯，堅持創作打卡瓜分現金大獎

總結

以上是生活随笔為你收集整理的【牛客 - 370 I 】Rinne Loves Xor（按位前缀和，异或）的全部內容，希望文章能夠幫你解決所遇到的問題。

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