CF1322 B. Present

发表于 | 阅读数

求$(a_1+a_2)\bigoplus(a_1+a_3)..(a_1+a_n)\bigoplus(a_2+a_3)…(a_{n-1}+a_{n})$

按位分别计算。
对于一位只有$a[i]+a[j]\in [2^k,2^{k+1}-1],[2^k+2^{k+1},2^{k+2}-2]$的数量会在二进制上异或产生影响。我们只保留$a[i]二进制的前k$位。

  • 寻找数量时，可以先排序，在用双指针维护一个区间，每次统计数量。
  • 如果从高位到低位，假设之前已经排序好，那么$a_i>=2^k$和$a_i<2^k$,$[1,i),[i,n]$已经排序好了。只需要归并一下即可
  • 如果朴素的统计，在第$k$位下$tmp=\sum_{i=1}^n\sum_{j=1}^n [a_i+a_j\in p]$正式的影响$k$位的数$=(tmp-\sum_{i=1}^n [a_i+a_i\in p])/2$,$p$为在所要求在的两个区间
代码 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <queue>
#include <cmath>
#include <cstring>
#include <vector>
#include <map>
using namespace std;
typedef long long ll;
const int N = 4e5 + 7;
int n, b[N], ans;

inline bool calc(int L, int R)
{
    if (L > R)
        return 0;
    ll ret = 0;
    for (int i = n, l = 1, r = 1; i; i--)
    {
        while (l <= n && b[i] + b[l] < L)
            ++l;
        while (r <= n && b[i] + b[r] <= R)
            ++r;
        ret += r - l - (l <= i && i < r);
    }
    return (ret >> 1) & 1;
}

inline bool solve(int k)
{

    int pos = n, md = 1 << (k + 1);
    for (int i = 1; i <= n; i++)
    {
        if (pos == n && b[i] >= md)
            pos = i;
        b[i] = b[i] & (md - 1);
    }
    //sort(b + 1, b + n + 1);
    inplace_merge(b + 1, b + pos, b + n + 1);
    return calc(1 << k, (1 << (k + 1)) - 1) ^ calc(3 << k, 4 * (1 << k) - 1);
}

int main()
{

    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        scanf("%d", &b[i]);
    sort(b + 1, b + n + 1);
    for (int i = 26; i >= 0; i--)
        ans |= solve(i) << i;
    cout << ans << endl;
    return 0;
}