灵茶八题 - 子数组 ^w^

灵茶八题 - 子数组 ^w

题目描述

给你一个长为 $n$ 的数组 $a$，输出它的所有连续子数组的异或和的异或和。

例如 $a=[1,3]$ 有三个连续子数组 $[1],[3],[1,3]$，异或和分别为 $1,3,2$，所以答案为 $1\oplus 3\oplus 2=0$。其中 $\oplus$ 表示异或运算。

输入格式

第一行输入一个整数 $n(1\le n\le 2\cdot 10^5)$。

第二行输入 $n$ 个非负整数，表示数组 $a$ 中的元素 $(0\le a[i]\le 10^9)$。

输出格式

一个整数，表示 $a$ 的所有连续子数组的异或和的异或和。

样例 #1

样例输入 #1

2
1 3

样例输出 #1

0

样例 #2

样例输入 #2

1
1

样例输出 #2

1

提示

由于只有^因此我们可以算每一个数的贡献，每一个数出现的次数为i * (n - i + 1),相当于把每个数出现了多少次都异或一下，出现次数为偶数则为0，奇数则为本身

#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];}//由于只有^因此我们可以算每一个数的贡献，每一个数出现的次数为i * (n - i + 1);//相当于把每个数出现了多少次都异或一下，出现次数为偶数则为0，奇数则为本身ll res = 0;for(ll i = 1; i <= n; i ++){res ^= ((i * (n - i + 1)) & 1) * a[i];}cout << res << endl;return 0;
}