cf——Sasha and a Bit of Relax（dp math）

关于异或运算，是可以求前缀和的。还有一些异或运算的性质

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。

1 #include <iostream> 2 using namespace std; 3 const int maxn=1<<21+5; 4 //const int maxn=1<<21; 5 int dp[2][maxn]; 6 int main() 7 { 8int n;scanf("%d",&n); 9dp[0][0]=1;10long long ans=0;11int num=0;12for(int i=1;i<=n;i++)13{14 int temp;scanf("%d",&temp);15 num=num^temp;16 ans+=dp[i%2][num];17 dp[i%2][num]++;18 19}20cout <<ans<<endl;21return 0;22 }

对了还有一个注意的就是左移的时候1<<21+5=1<<26;(1<<21)+5这样才对

al⊕al+1⊕…⊕amid=amid+1⊕amid+2⊕…⊕ar

如果觉得《cf——Sasha and a Bit of Relax（dp math）》对你有帮助，请点赞、收藏，并留下你的观点哦！