靈茶八題 - 子數(shù)組 ^w

題目描述

給你一個(gè)長(zhǎng)為 $n$ 的數(shù)組 $a$，輸出它的所有連續(xù)子數(shù)組的異或和的異或和。

例如 $a=[1,3]$ 有三個(gè)連續(xù)子數(shù)組 $[1],[3],[1,3]$，異或和分別為 $1,3,2$，所以答案為 $1\oplus 3\oplus 2=0$。其中 $\oplus$ 表示異或運(yùn)算。

輸入格式

第一行輸入一個(gè)整數(shù) $n(1\le n\le 2?10^5)$。

第二行輸入 $n$ 個(gè)非負(fù)整數(shù)，表示數(shù)組 $a$ 中的元素 $(0\le a[i]\le 10^9)$。

輸出格式

一個(gè)整數(shù)，表示 $a$ 的所有連續(xù)子數(shù)組的異或和的異或和。

樣例 #1

樣例輸入 #1

2
1 3

樣例輸出 #1

0

樣例 #2

樣例輸入 #2

1
1

樣例輸出 #2

1

提示

由于只有^因此我們可以算每一個(gè)數(shù)的貢獻(xiàn)，每一個(gè)數(shù)出現(xiàn)的次數(shù)為i * (n - i + 1),相當(dāng)于把每個(gè)數(shù)出現(xiàn)了多少次都異或一下，出現(xiàn)次數(shù)為偶數(shù)則為0，奇數(shù)則為本身

#include<bits/stdc++.h>using namespace std;typedef long long ll;
typedef pair<int, int>PII;
const int N=2e5+10;
const int MOD = 998244353;
const int INF=0X3F3F3F3F;
const int dx[]={-1,1,0,0,-1,-1,+1,+1};
const int dy[]={0,0,-1,1,-1,+1,-1,+1};
const int M = 1e7 + 10;int t;int a[N];
int main()
{int n;cin >> n;for(int i = 1; i <= n; i ++){cin >> a[i];}//由于只有^因此我們可以算每一個(gè)數(shù)的貢獻(xiàn)，每一個(gè)數(shù)出現(xiàn)的次數(shù)為i * (n - i + 1);//相當(dāng)于把每個(gè)數(shù)出現(xiàn)了多少次都異或一下，出現(xiàn)次數(shù)為偶數(shù)則為0，奇數(shù)則為本身ll res = 0;for(ll i = 1; i <= n; i ++){res ^= ((i * (n - i + 1)) & 1) * a[i];}cout << res << endl;return 0;
}