Problem Statement

?

You are given two integer sequences, each of length?N:?a₁,…,a_N?and?b₁,…,b_N.

There are?N²?ways to choose two integers?i?and?j?such that?1≤i,j≤N. For each of these?N²?pairs, we will compute?a_i+b_j?and write it on a sheet of paper. That is, we will write?N²?integers in total.

Compute the XOR of these?N²?integers.

?

Definition of XOR

?

Constraints

?

• All input values are integers.
• 1≤N≤200,000
• 0≤a_i,b_i<2²⁸

Input

?

Input is given from Standard Input in the following format:

N a₁ a₂ … a_N b₁ b₂ … b_N

Output

?

Print the result of the computation.

Sample Input 1

?

2 1 2 3 4

Sample Output 1

?

2

On the sheet, the following four integers will be written:?4(1+3),5(1+4),5(2+3)and?6(2+4).

Sample Input 2

?

6 4 6 0 0 3 3 0 5 6 5 0 3

Sample Output 2

?

8

Sample Input 3

?

5 1 2 3 4 5 1 2 3 4 5

Sample Output 3

?

2

Sample Input 4

?

1 0 0

Sample Output 4

?

0


題意：
給你兩個(gè)含有n個(gè)數(shù)的數(shù)組a,b
然后我們對每一個(gè)a[i] 加上 b[j] 得到的數(shù)，把這些數(shù)全部異或起來，問最后的異或值是多少？

思路：
首先我們對每一個(gè)數(shù)進(jìn)行二進(jìn)制拆分，對每一位進(jìn)行討論，
只需要討論二進(jìn)制的第x位，在所有相加出來得到的數(shù)中是奇數(shù)個(gè)還是偶數(shù)個(gè)，
如果是奇數(shù)個(gè)就對答案有貢獻(xiàn)，貢獻(xiàn)值為 1<<x，偶數(shù)個(gè)就沒有貢獻(xiàn)。
然后問題轉(zhuǎn)化為 我們要咋知道 有多少對 a[i] + b[j] 的第x位為1

由于我們每一步只討論a[i]+b[j] 的第x位，我們可以只看a[i] 和 b[j] 的 二進(jìn)制后 x 位，
因?yàn)槲覀冎恍枰紤] x位的情況就知道了 a[i]+b[j] 的 第x位情況，
那么我們在枚舉第x位的時(shí)候，把a(bǔ)，b數(shù)組對 2的x+1次方 取模 ，即可得到每個(gè)數(shù)的二進(jìn)制后x位。

然后利用這個(gè)結(jié)論， 對于一對數(shù) a[i] +b[j] = num， 如果我們想要num的二進(jìn)制第x位為1，需要滿足：
num <= a[i]+b[j] <2*num
3*num <= a[i]+b[j] < 4*num

這樣我們就可以在每一次取模后的數(shù)組，對其中一個(gè)數(shù)組進(jìn)行排序，然后利用二分找到滿足條件的區(qū)間，
通過區(qū)間的長度相加以來判定最終的滿足x位是1的數(shù)量的奇偶性，來判定 是否在答案上加上貢獻(xiàn)。

#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #include <cmath> #include <queue> #include <stack> #include <map> #include <set> #include <vector> #include <iomanip> #define ALL(x) (x).begin(), (x).end() #define rt return #define dll(x) scanf("%I64d",&x) #define xll(x) printf("%I64d\n",x) #define sz(a) int(a.size()) #define all(a) a.begin(), a.end() #define rep(i,x,n) for(int i=x;i<n;i++) #define repd(i,x,n) for(int i=x;i<=n;i++) #define pii pair<int,int> #define pll pair<long long ,long long> #define gbtb ios::sync_with_stdio(false),cin.tie(0),cout.tie(0) #define MS0(X) memset((X), 0, sizeof((X))) #define MSC0(X) memset((X), '\0', sizeof((X))) #define pb push_back #define mp make_pair #define fi first #define se second #define eps 1e-6 #define gg(x) getInt(&x) #define db(x) cout<<"== [ "<<x<<" ] =="<<endl; using namespace std; typedef long long ll; ll gcd(ll a, ll b) {return b ? gcd(b, a % b) : a;} ll lcm(ll a, ll b) {return a / gcd(a, b) * b;} ll powmod(ll a, ll b, ll MOD) {ll ans = 1; while (b) {if (b % 2)ans = ans * a % MOD; a = a * a % MOD; b /= 2;} return ans;} inline void getInt(int* p); const int maxn = 1000010; const int inf = 0x3f3f3f3f; /*** TEMPLATE CODE * * STARTS HERE ***/ int a[maxn]; int b[maxn]; int n; int c[maxn]; int d[maxn]; int main() {//freopen("D:\\common_text\\code_stream\\in.txt","r",stdin);//freopen("D:\\common_text\\code_stream\\out.txt","w",stdout); gbtb;cin >> n;repd(i, 1, n){cin >> a[i];}repd(i, 1, n){cin >> b[i];}int base = 1;ll ans = 0ll;for (int i = 0; i <= 28; i++){repd(j, 1, n){c[j] = a[j] % (2 * base);d[j] = b[j] % (2 * base);}sort(d + 1, d + 1 + n);int num = 0;repd(j, 1, n){int r = lower_bound(d + 1, d + 1 + n, 2 * base - c[j]) - d - 2;int l = lower_bound(d + 1, d + 1 + n, base - c[j]) - d - 1;num += r - l + 1;r = lower_bound(d + 1, d + 1 + n, 4 * base - c[j]) - d - 2;l = lower_bound(d + 1, d + 1 + n, 3 * base - c[j]) - d - 1;num += r - l + 1;}if (num & 1){ans += 1ll * base;}base *= 2;}cout << ans << endl;return 0; }inline void getInt(int* p) {char ch;do {ch = getchar();} while (ch == ' ' || ch == '\n');if (ch == '-') {*p = -(getchar() - '0');while ((ch = getchar()) >= '0' && ch <= '9') {*p = *p * 10 - ch + '0';}}else {*p = ch - '0';while ((ch = getchar()) >= '0' && ch <= '9') {*p = *p * 10 + ch - '0';}} }

?

轉(zhuǎn)載于:https://www.cnblogs.com/qieqiemin/p/10828624.html

總結(jié)

以上是生活随笔為你收集整理的AtCoder Regular Contest 092 Two Sequences AtCoder - 3943 （二进制+二分）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。