网站做得好的公司,丽水做网站,百度搜索排名优化哪家好,wordpress网站模板怎么用灵茶八题 - 子数组 w
题目描述
给你一个长为 n n n 的数组 a a a#xff0c;输出它的所有连续子数组的异或和的异或和。
例如 a [ 1 , 3 ] a[1,3] a[1,3] 有三个连续子数组 [ 1 ] , [ 3 ] , [ 1 , 3 ] [1],[3],[1,3] [1],[3],[1,3]#xff0c;异或和分别为 1 , 3 , …灵茶八题 - 子数组 w
题目描述
给你一个长为 n n n 的数组 a a a输出它的所有连续子数组的异或和的异或和。
例如 a [ 1 , 3 ] a[1,3] a[1,3] 有三个连续子数组 [ 1 ] , [ 3 ] , [ 1 , 3 ] [1],[3],[1,3] [1],[3],[1,3]异或和分别为 1 , 3 , 2 1,3,2 1,3,2所以答案为 1 ⊕ 3 ⊕ 2 0 1 \oplus 3\oplus 20 1⊕3⊕20。其中 ⊕ \oplus ⊕ 表示异或运算。
输入格式
第一行输入一个整数 n ( 1 ≤ n ≤ 2 ⋅ 1 0 5 ) n\ (1\le n \le 2\cdot 10^5) n (1≤n≤2⋅105)。
第二行输入 n n n 个非负整数表示数组 a a a 中的元素 ( 0 ≤ a [ i ] ≤ 1 0 9 ) (0\le a[i] \le 10^9) (0≤a[i]≤109)。
输出格式
一个整数表示 a a a 的所有连续子数组的异或和的异或和。
样例 #1
样例输入 #1
2
1 3样例输出 #1
0样例 #2
样例输入 #2
1
1样例输出 #2
1提示
由于只有^因此我们可以算每一个数的贡献每一个数出现的次数为i * (n - i 1),相当于把每个数出现了多少次都异或一下出现次数为偶数则为0奇数则为本身
#includebits/stdc.husing namespace std;typedef long long ll;
typedef pairint, intPII;
const int N2e510;
const int MOD 998244353;
const int INF0X3F3F3F3F;
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;
}
