本文共 3240 字,大约阅读时间需要 10 分钟。
time limit per test: 1 second
memory limit per test: 256 megabytesinput: standard inputoutput: standard output
Sasha likes programming. Once, during a very long contest, Sasha decided that he was a bit tired and needed to relax. So he did. But since Sasha isn’t an ordinary guy, he prefers to relax unusually. During leisure time Sasha likes to upsolve unsolved problems because upsolving is very useful.
Therefore, Sasha decided to upsolve the following problem:
You have an array with integers. You need to count the number of funny pairs . To check if a pair is a funny pair, take , then if is an even number and , then the pair is funny. In other words, of elements of the left half of the subarray from to should be equal to of elements of the right half. Note that denotes the .
It is time to continue solving the contest, so Sasha asked you to solve this task.
Input
The first line contains one integer — the size of the array.
The second line contains integers — array itself.
Output
Print one integer — the number of funny pairs. You should consider only pairs where is even number.
Examples
input
51 2 3 4 5
output
1
input
63 2 2 3 7 6
output
3
input
342 4 2
output
0
Note
Be as cool as Sasha, upsolve problems!
In the first example, the only funny pair is , as .
In the second example, funny pairs are , , and .
In the third example, there are no funny pairs.
题意
有 个数,对于偶数长度的区间 , ,要求 两个区间内的数的异或值相等,问有多少个这样的区间
Solve
利用异或的性质:出现偶数次的数异或值为
如果 区间数的异或值相等,则 区间的数的异或值为
可以推出:如果当前位置的异或值出现过,并且之前出现的位置与当前出现位置下标的奇偶性相同,那么这两个位置之间的区域就是题目中要求的funny pairs
Code
/************************************************************************* > File Name: C.cpp > Author: WZY > Created Time: 2019年02月17日 19:59:36 ************************************************************************/#include#define ll long long#define ull unsigned long long#define ms(a,b) memset(a,b,sizeof(a))#define pi acos(-1.0)#define INF 0x7f7f7f7fconst double E=exp(1);const int maxn=1e6+10;const int mod=1e9+7;using namespace std;ll sum[1<<20][2];int main(int argc, char const *argv[]){ ios::sync_with_stdio(false); cin.tie(0); int n; cin>>n; ll ans=0; ll x; ll res=0; sum[0][0]=1; for(int i=1;i<=n;i++) { cin>>x; res^=x; ans+=sum[res][i&1]; sum[res][i&1]++; } cout< <
转载地址:https://www.cnblogs.com/Friends-A/p/11054964.html 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!