CF1109
CF1109A
CF1109A题意
给定一个含 \(n\) 个整数的序列 \(a\)，定义 \((l,r)\) 是一个funny pair当且仅当 \(r>l,r-l+1\) 为偶数，且 \(a\) 中下标自 \(l\) 到 \(\frac{l+r-1}2\) 的数的异或和等于下标自 \(\frac{l+r-1}2+1\) 到 \(r\) 的数的异或和。求序列 \(a\) 中funny pairs的个数。
CF1109A题解
首先想到前缀和，然后 \(s_l\oplus s_{mid}=s_{mid}\oplus s_r\)，然后发现 \(s_l=s_r\)。
然后就没了。
CF1109A代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
inline int read(){
int x = 0, f= 1;char ch = getchar();
while(ch < '0' || ch > '9'){if(ch == '-') f = -1;ch = getchar();}
while(ch >= '0' && ch <= '9'){x = (x << 1) + (x << 3) + (ch ^ 48);ch = getchar();}
return x * f;
}
map<int,int> mp1,mp2;
int n;
signed main(){
n = read();int sum = 0,ans = 0;
mp2[0]++;
for(int i = 1;i <= n;i++){
sum ^= read();
if(i & 1){ans += mp1[sum];mp1[sum]++;}
else {ans += mp2[sum];mp2[sum]++;}
}
printf("%lld\n",ans);
return 0;
}