题解:求一个序列问长度为偶数且在[L, R]范围内的异或和的和,这个题考察的异或和的问题,因为异或和的话就要牵扯到二进制,所以一般来说这类问题就是将其拆开来进行计算。
首先:异或计算
1xor1=0,0xor0=0,1xor0=1
很容易可以得到一个结论,就是在某位上的时候,只有1才会影响到他的值,当1的个数为奇数时,二进制那个位置上才会计算出1这个数字。因为此题是处理一个区间的问题,为了减少时间复杂度,我们可以用到前缀和这个工具就是这样子
for(int i=1;i<=n;i++){ scanf("%d",&a[i]); a[i]=a[i]^a[i-1]; }
这个题又有一个条件:保证区间为偶数,所以
if(l&1) l++; if(r&1) r--;
接下来枚举二进制的1-32位每个位置的情况,计算出最终结果每一位上有多少个1是在符合条件的亦或过程中产生的,然后加权求和就可以。因为这个题目需要的区间是偶数长度的区间,因此如果j是奇数,则以j为右边界的满足条件的区间的左边界肯定都是奇数。如果j是偶数,则以j为右边界的满足条件的区间的左边界肯定都是偶数。因此为了计算满足以第j个数字为结尾的符合条件的区间其第i位的贡献,所以我们需要分奇数和偶数。
代码:
#pragma GCC optimize(3,"Ofast","inline") #include <bits/stdc++.h> const int maxn = 1e5+10; const int MaxN = 0x3f3f3f3f; const int MinN = 0xc0c0c00c; typedef long long ll; const int mod = 1e9+7; using namespace std; int a[maxn]; int dp[10][10]; int main() { int n,l,r; cin>>n>>l>>r; if(l==r){ cout<<0<<endl; return 0; } for(int i=1;i<=n;i++){ scanf("%d",&a[i]); a[i]=a[i]^a[i-1]; } if(l&1) l++; if(r&1) r--; ll ans=0; for(int i=0;i<32;i++){ memset(dp,0,sizeof(dp)); ll sum=0,temp=1<<i; for(int j=l;j<=n;j++){ dp[(a[j-l]>>i)&1][(j-l)&1]++; sum+=dp[((a[j]>>i)&1)^1][j&1]; if(j>=r) dp[(a[j-r]>>i)&1][(j-r)&1]--; } ans=(ans+temp*sum%mod)%mod; } cout<<ans<<endl; return 0; }