![cf——Sasha and a Bit of Relax(dp,math) cf——Sasha and a Bit of Relax(dp,math)](https://image.shishitao.com:8440/aHR0cHM6Ly9ia3FzaW1nLmlrYWZhbi5jb20vdXBsb2FkL2NoYXRncHQtcy5wbmc%2FIQ%3D%3D.png?!?w=700&webp=1)
关于异或运算,是可以求前缀和的。还有一些异或运算的性质
0^a=a;
交换律 a^b=b^a
结合律 a^(b^c)=(a^b)^c
分配率 a^(b+c)=a^b+a^c
自反律 a^b^b=a
判断两个数是否相等 a^b=0
这个题真的学到好多
要找 al⊕al+1⊕…⊕amid=amid+1⊕amid+2⊕…⊕ar,即
0=al⊕al+1⊕…⊕amid⊕amid+1⊕amid+2⊕…⊕ar;
然后用一个sum数组保留前缀异或。
对于要求r-l+1是偶数,那么l,r一定不同奇偶。
只要找(l-1)+r同奇偶就可以了,枚举r从1-n。
#include <iostream>
using namespace std;
const int maxn=<<+;
//const int maxn=1<<21;
int dp[][maxn];
int main()
{
int n;scanf("%d",&n);
dp[][]=;
long long ans=;
int num=;
for(int i=;i<=n;i++)
{
int temp;scanf("%d",&temp);
num=num^temp;
ans+=dp[i%][num];
dp[i%][num]++; }
cout <<ans<<endl;
return ;
}
对了还有一个注意的就是左移的时候1<<21+5=1<<26;(1<<21)+5这样才对
al⊕al+1⊕…⊕amid=amid+1⊕amid+2⊕…⊕ar