【题解】CF1322B Present

Statement

给定一个长度为 $n$ 的数列 $a$，求

$$\oplus_{i = 1}^{n} \oplus_{j = i + 1}^{n} (a_i + a_j)$$

其中 $1 \le n \le 4 \times 10^5$，$\forall i,1 \le i \le n,1 \le a_i \le 10^7$。

Solution

简单的双重暴力显然是会超时的，问题的关键在于如何将两重循环减少一层。

对于异或等位运算操作，其特殊的性质在于按位运算，即每一位的影响不会改变下一层。

因此不难想到将答案二进制后的每一位进行讨论，最后统计答案。

• 对于第 $k$ 位：

  讨论两个数之和的二进制表示在第 $k$ 位上是否为 $1$，根据加法的性质，我们只需要得知这两个数的前 $k$ 位是多少。

  定义数组 $b$，对于 $\forall b_i$，都有 $b_i \gets a_i \wedge (2 ^ {k + 1} - 1)$。

  接着，我们讨论两个数（不妨设为 $b_x, b_y$）可行的条件：

  由于对于数组 $b$，$(b_x + b_y)$ 的范围为 $[0,2 \times (2^{i + 1} - 1)]$，因此两个数可能会有两种情况：

  1. 在第 $k$ 位不进位：$b_x + b_y \in [2^k, 2 ^ {i + 1} - 1]$​。
  2. 在第 k 位最多只进一位：$b_x + b_y \in [2 \times 2^k, 2 \times (2^{i + 1} - 1)]$。

​ 通过统计这两种方案的个数，根据异或的性质，当且仅当总方案为奇数时，说明 $1 \le i \le n, i + 1 \le j \le n$ 对于第 $k$ 位的贡献为 $1$，即 $ans$ 在第 $k$ 位上的二进制数为 $1$。

问题就在于如何以较低的复杂度求出满足一定范围的 $b$ 数组元素的个数。

可以先将数组 $b$ 进行排序，求范围个数不难想到双指针，定义两个指针分别指向满足左/右边界的最值，相减即为答案。由于序列 b 的单调性，当其中一个数单调上升，另外一个数成立的范围必然单调非递减，不妨让循环元素倒序遍历，这样就可以保证答案的正确性。

$tips:$ 两个元素从两头遍历，答案会被统计两次，因此要除以 $2$。

总的时间复杂度为 $\mathcal{O} (n \log n \log w)$，其中 $n$ 为元素个数，$w$ 为值域。

Code

1
2
3
4
5
6
7
8
9

bool solve(int k)    // 按位讨论
{
    for (int i = 1; i <= n; i ++)
        // b[i] = a[i] % (1 << (k + 1));
        b[i] = a[i] & (1 << (K + 1) - 1);	// 两种写法均可
    
    sort(b + 1, b + 1 + n);	// 满足序列单调性质
    return work(1 << k, (1 << (k + 1)) - 1) ^ work(3 << k, (1 << (k + 2)) - 2);
}

1
2
3
4
5
6
7
8
9
10
11
12
13

bool work(int lft, int rht)    // 双指针
{
    if (lft > rht) return false;	// 特判
    
    int cnt = 0;
    for (int l = 1, r = 1, i = n; i >= 1; i --)
    {
        while (l <= n && b[i] + b[l] < lft) l ++;
        while (r <= n && b[i] + b[r] <= rht) r ++;
        cnt += r - l - (l <= i && i < r);	// 当 i 在 l 和 r 之间时不可被统计
    }
    return (cnt >> 1) & 1;	// 注意重复统计
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14

signed main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    cin >> n;
    for (int i = 1; i <= n; i ++)
        cin >> a[i];
    
    for (int k = 0; k < 26; k ++)
        ans += solve(k) << k;	// 第 k 位的贡献为 (1 << k)
        
    cout << ans << '\n';
        
    return 0;
}