1. 異或和之和

1.題目描述

給定一個(gè)數(shù)組 $A_i$，分別求其每個(gè)子段的異或和，并求出它們的和?；蛘哒f(shuō)，對(duì)于每組滿足 $1\le L\le R\le n$ 的 $L,R$，求出數(shù)組中第 $L$ 至第 $R$ 個(gè)元素的異或和。然后輸出每組 $L,R$ 得到的結(jié)果加起來(lái)的值。

2.輸入格式

輸入的第一行包含一個(gè)整數(shù) $n$。

第二行包含 $n$ 個(gè)整數(shù) $A_i$，相鄰整數(shù)之間使用一個(gè)空格分隔。

3.輸出格式

輸出一行包含一個(gè)整數(shù)表示答案。

4.樣例輸入

5
1 2 3 4 5

5.樣例輸出

39

6. 數(shù)據(jù)范圍

對(duì)于 $30\%$ 的評(píng)測(cè)用例，$n\le 300$；

對(duì)于 $60\%$ 的評(píng)測(cè)用例，$n\le 5000$；

對(duì)于所有評(píng)測(cè)用例，$1\le n\le 10^5$，$0\le A_i\le 2^{20}$。

7. 原題鏈接

異或和之和

2. 解題思路

首先，根據(jù)題意進(jìn)行暴力枚舉每個(gè)子區(qū)間 $[l,r]$ $(1\le l\le r\le n)$ 的異或和，復(fù)雜度將是 $O(n^2)$，無(wú)法通過(guò)本題，但可以拿到一定分?jǐn)?shù)。

因?yàn)樯婕爱惢蜻\(yùn)算且觀察到 $a_i$ 的取值范圍為 $[0,2^{20}]$，我們不難想到從"拆位"的角度去思考問(wèn)題。假設(shè)對(duì)于二進(jìn)制位的第 $i\in [0,20]$ 位，數(shù)組中一共有 $x$ 個(gè)子區(qū)間在該位的異或和為 $1$，那么該位對(duì)答案的貢獻(xiàn)為 $2^i\times x$。這樣我們就將整個(gè)大問(wèn)題，拆成了 $20$ 個(gè)子問(wèn)題，原數(shù)組相當(dāng)于被我們拆分為 $20$ 個(gè) $01$ 數(shù)組。

對(duì)于每個(gè)子問(wèn)題，也就是對(duì)于每個(gè) $01$ 數(shù)組，我們需要求出有多少子數(shù)組的異或和為 $1$，也就是求出前面所說(shuō)的 $x$。這個(gè)問(wèn)題我們可以通過(guò)前綴異或來(lái)解決。設(shè)這里的 $01$ 數(shù)組為 $a$ 數(shù)組，我們?cè)僭O(shè)一個(gè) $S$ 數(shù)組，$S_i$ 表示 $a$ 數(shù)組中前 $i$ 個(gè)元素的異或和為多少。根據(jù)異或運(yùn)算的性質(zhì)：

$$a_i\oplus a_{i+1}\oplus ?\oplus a_{j?1}\oplus a_j=(a_1\oplus a_2\oplus ?a_j)\oplus (a_1\oplus a_2\oplus ?\oplus a_{i?1})$$

將上述式子用 $S$ 進(jìn)行代替有：

$$a_i\oplus a_{i+1}\oplus ?\oplus a_{j?1}\oplus a_j=S_{i?1}\oplus S_j$$

如果想使得等式左邊等于 $1$，即需要滿足 $S_{i?1}\ne S_j$。

根據(jù)上述分析，我們可以枚舉每個(gè) $01$ 數(shù)組的前綴異或數(shù)組 $S$，當(dāng)我們枚舉到 $S_j$ 時(shí)，我們只需要考慮在它之前有多少個(gè) $S_i$ 和它不同，不同的個(gè)數(shù)就等于以 $a_j$ 結(jié)尾且異或和為 $1$ 的子數(shù)組個(gè)數(shù)，這個(gè)統(tǒng)計(jì)個(gè)數(shù)的功能我們可以使用哈希表實(shí)現(xiàn)。

這樣我們可以在接近 $O(n)$ 的復(fù)雜度統(tǒng)計(jì)出每個(gè) $01$ 數(shù)組子區(qū)間異或?yàn)?$1$ 的個(gè)數(shù)，我們?cè)O(shè)第 $i$ 個(gè)二進(jìn)制位的 $01$ 數(shù)組子區(qū)間異或?yàn)?$1$ 的個(gè)數(shù)為 $b_i$，最終答案為：

$$\sum _{i=0}^{20}{2}^i\times b_i$$

時(shí)間復(fù)雜度：$O(20\times n)$。文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-640318.html

3. AC_Code

• C++

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 100010;

int n;
int a[N][25];
int main()
{
	ios_base :: sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	cin >> n;
	for (int i = 1; i <= n; ++i) {
		int x;
		cin >> x;
		for (int j = 0; j <= 20; ++j) {
			a[i][j] = (x >> j) & 1;
			a[i][j] ^= a[i - 1][j];
		}
	}
	LL ans = 0;
	for (int j = 0; j <= 20; ++j) {
		map<int, int> m;
		m[0]++;
		for (int i = 1; i <= n; ++i) {
			int x = m[a[i][j] ^ 1];
			ans += 1LL * (1 << j) * x;
			m[a[i][j]]++;
		}
	}
	cout << ans << '\n';
	return 0;
}

• Java

import java.util.*;

public class Main {
    static final int N = 100010;

    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        int[][] a = new int[N][25];
        for (int i = 1; i <= n; ++i) {
            int x = scan.nextInt();
            for (int j = 0; j <= 20; ++j) {
                a[i][j] = (x >> j) & 1;
                a[i][j] ^= a[i - 1][j];
            }
        }
        long ans = 0;
        for (int j = 0; j <= 20; ++j) {
            Map<Integer, Integer> m = new HashMap<>();
            m.put(0, 1);
            for (int i = 1; i <= n; ++i) {
                int x = m.getOrDefault(a[i][j] ^ 1, 0);
                ans += (1L << j) * x;
                m.put(a[i][j], m.getOrDefault(a[i][j], 0) + 1);
            }
        }
        System.out.println(ans);
    }
}

• Python

n = int(input())
N = 100010
a = [[0] * 25 for _ in range(N)]
b = list(map(int, input().split()))
for i in range(1, n + 1):
    x = b[i-1]
    for j in range(21, -1, -1):
        a[i][j] = (x >> j) & 1
        a[i][j] ^= a[i - 1][j]
ans = 0
for j in range(21, -1, -1):
    m = {0: 1}
    for i in range(1, n + 1):
        x = m.get(a[i][j] ^ 1, 0)
        ans += (1 << j) * x
        m[a[i][j]] = m.get(a[i][j], 0) + 1
print(ans)

到了這里，關(guān)于第十四屆藍(lán)橋杯省賽 C/C++ A 組 H 題——異或和之和（AC）的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！