这一题我是只想到暴力的 t了后面想到了以前写的一些题就算了二进制的前缀和
但还是t了 于是在学习了一番博客后 我学会了
我们先统计二进制前缀和 然后在统计前缀和的奇偶数的前缀和 因为要统计长度为偶数
所有是以二一跳的前缀和 有了这以后 我们枚举左端点 就可以O(1)求右端点以及贡献
对于范围lr 就从把1n改为lr
#include <bits/stdc++.h> #define ll long long const int N=1e5+5; const int p=1e9+7; using namespace std; int n,l,r,a[N],b[N],f[N][31],dp[N][31][2]; int main() { ios::sync_with_stdio(false); cin>>n>>l>>r; for(int i=1;i<=n;++i)cin>>a[i]; for(int i=1;i<=n;++i) { for(int j=29;j>=0;--j) { f[i][j]=f[i-1][j]+((a[i]>>j)&1);///二进制前缀和 if(i!=1) { dp[i][j][0]=dp[i-2][j][0];///以二一跳的奇偶数前缀和 dp[i][j][1]=dp[i-2][j][1]; } ++dp[i][j][f[i][j]&1];///当前是奇是哦 } } ll ans=0; for(int i=1;i<=n;++i)///枚举左端点 { int L=i+l-1,R=min(i+r-1,n);///最短与最长区间长度 if((L-i+1)&1){///不能提前处理 l r ++L; } if((R-i+1)&1){ --R; } if(L>R) continue; for(int j=29;j>=0;--j) { int k=((f[i-1][j]&1)^1);///相反位数 本来是奇 求偶数个数 ll ins=dp[R][j][k]; if(L!=1) { ins-=dp[L-2][j][k]; } ans+=(ins*(1<<j))%p,ans%=p;///算贡献 } // cout<<ans<<endl; } cout<<ans<<endl; return 0; }