19 蓝桥真题：异或和之和

2023 C++ A 组 T8. 异或和之和

前言

「算法题解」系列致力于分享有价值的题目、探讨更优秀的解法。

这是本系列的第 19 篇题解，更多题解关注 Somnia1337@力扣。

题目描述

本题目的在线练习：

• 洛谷

https://www.luogu.com.cn/problem/P9236

• Dotcpp

https://www.dotcpp.com/oj/problem3147.html

洛谷：普及+/提高

Dotcpp：中等

给定一个数组 a，分别求其每个子数组的异或和，并输出它们的和。

「输入」

第一行包含一个整数 n。

第二行包含 n 个整数 a[i]，相邻整数之间使用一个空格分隔。

「输出」

一个整数，表示答案。

「样例」

输入：

5
1 2 3 4 5

输出：

39

解题思路

位运算具有自反性，即 $x\oplus y\oplus y=x$。

类比前缀和，对 $a$ 求前缀异或和，记 $P_i=a_1\oplus a_2\oplus \cdots \oplus a_i$，则子数组 $a[l:r]$ 的异或和为 $P_{l-1}\oplus P_r$。

对两个前缀异或和 $P_1$ 和 $P_2$，按位对齐之后，异或为 $0$ 的位不会对答案产生贡献，为 $1$ 的位产生 $2^d$ 的贡献，其中 $d$ 为该位所在位数。

但是，不能遍历每对前缀和（复杂度 $O(N^2)$ 过高），而需要按位遍历。

对每一位 $d$，遍历 $P$，计数 $0$ 和 $1$ 的数量，用组合数学可得该位对答案的贡献为 $2^d\times cnt[0]\times cnt[1]$。

实现时，只需使用 $a$ 的前缀和，在 $a$ 中原地前缀化即可。

复杂度

• 时间复杂度：$O(N)$，按位遍历产生常数 $20$。
• 空间复杂度：$O(N)$。

代码

Java

import java.util.*;
import java.io.*;
 
public class Main {
    public static void main(String... args) throws IOException {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        PrintWriter out = new PrintWriter(System.out);
		
        // 输入
        int n = Integer.parseInt(in.readLine());
        long[] a = new long[n + 1]; // 多开 1, 原地前缀化
        StringTokenizer st = new StringTokenizer(in.readLine());
        // 输入的同时求前缀异或和
        for (int i = 1; i <= n; i++) a[i] = Integer.parseInt(st.nextToken()) ^ a[i - 1];
		
        // 处理
        long ans = 0;
        // 按位遍历, 最多 20 位
        for (int d = 0; d <= 20; d++) {
            // 计数 0 和 1
            int[] cnt = new int[2];
            for (int i = 0; i <= n; i++) cnt[(int) (a[i] >> d & 1)]++;
            // 累加贡献
            ans += (1L << d) * cnt[0] * cnt[1];
        }
		
        // 输出
        out.println(ans);
		
        out.flush();
        out.close();
    }
}

最后

更多系列「外源推文」&「生活分享」关注公众号：