打卡信奥刷题（2784）用C++实现信奥题 P3917 异或序列

P3917 异或序列

题目描述

给出序列A 1 , A 2 , ⋯ , A N A_1,A_2,\cdots,A_NA1​,A2​,⋯,AN​，求

∑ 1 ≤ i ≤ j ≤ N A i ⊕ A i + 1 ⊕ ⋯ ⊕ A j \sum_{1\le i\le j\le N} A_i\oplus A_{i+1}\oplus\cdots\oplus A_j1≤i≤j≤N∑​Ai​⊕Ai+1​⊕⋯⊕Aj​

的值。其中，⨁ \bigoplus⨁表示按位异或。

输入格式

第一行，一个整数N NN。

第二行，N NN个整数A 1 , A 2 , ⋯ , A N A_1,A_2,\cdots,A_NA1​,A2​,⋯,AN​。

输出格式

一个数，为表达式的值。

输入输出样例 #1

输入 #1

2 1 2

输出 #1

6

说明/提示

• 对于60 % 60\%60%的数据，1 ≤ N ≤ 10 3 1 \le N \le 10^31≤N≤103；
• 对于100 % 100\%100%的数据，1 ≤ N ≤ 10 5 1 \le N \le 10^51≤N≤105，0 ≤ A i ≤ 10 9 0 \le A_i \le 10^90≤Ai​≤109。

C++实现

#include<iostream>#include<cstdio>#include<cstdlib>#include<cstring>#include<string>#include<algorithm>#include<math.h>usingnamespacestd;intn,a,dp[32];longlongans;intmain(){inti,j;scanf("%d",&n);for(i=1;i<=n;++i){scanf("%d",&a);for(j=31;j>-1;--j){if(a&(1<<j))dp[j]=i-dp[j];ans+=1LL*dp[j]*(1<<j);}}printf("%lld",ans);return0;}

后续

接下来我会不断用C++来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现，记录日常的编程生活、比赛心得，感兴趣的请关注，我后续将继续分享相关内容