自己做網(wǎng)站好不好小紅書推廣方式有哪些
靈茶八題 - 子數(shù)組 w
題目描述
給你一個(gè)長(zhǎng)為 n n n 的數(shù)組 a a a,輸出它的所有連續(xù)子數(shù)組的異或和的異或和。
例如 a = [ 1 , 3 ] a=[1,3] a=[1,3] 有三個(gè)連續(xù)子數(shù)組 [ 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 2=0 1⊕3⊕2=0。其中 ⊕ \oplus ⊕ 表示異或運(yùn)算。
輸入格式
第一行輸入一個(gè)整數(shù) n ( 1 ≤ n ≤ 2 ? 1 0 5 ) n\ (1\le n \le 2\cdot 10^5) n?(1≤n≤2?105)。
第二行輸入 n n n 個(gè)非負(fù)整數(shù),表示數(shù)組 a a a 中的元素 ( 0 ≤ a [ i ] ≤ 1 0 9 ) (0\le a[i] \le 10^9) (0≤a[i]≤109)。
輸出格式
一個(gè)整數(shù),表示 a a 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;
}