题解:
很套路的一道题:由于所求的是异或之和,我们知道位运算不产生进位,所以每个数位与位之间的贡献是独立的,不想不影响,那么我们考虑按位计算对 答案的贡献即可,
令pre[i][j]表示 前i个数中第j位为1的个数,那么当我们枚举所有区间的左端点i时,如果pre[i-1][j]是奇数,那么所有能对答案造成贡献的右端点r的pre[r][j]一定是偶数,反之亦然。
所以,我们在令cnt[i][j]表示前i个数中,pre[i][j]为奇数的个数,但是题目还有一个限制条件就是长度必须是偶数,所以我们把cnt[i][j]表示前面与i奇偶性相同的个数,
这样,当我们枚举所有区间的左端点i时,就可以O1的计算答案了~
代码:
#include<bits/stdc++.h> #define ls rt<<1 #define rs rt<<1|1 #define fi first #define se second #define pb push_back #define DEBUG(x) std::cerr << #x << '=' << x << std::endl using namespace std; typedef long long ll; typedef vector<int> VI; typedef pair<int,int> pii; typedef pair<ll,ll> pll; const ll inf = 0x3f3f3f3f3f3f3f3f; const int mod = 1e9+7; const int maxn = 1e5 + 4; const int N = 5e3 + 5; const double eps = 1e-6; const double pi = acos(-1); ll qpow(ll x,ll y){ll ans=1;x%=mod;while(y){ if(y&1) ans=ans*x%mod; x=x*x%mod; y>>=1;}return ans;} int n,l,r,pre[maxn][31],cnt[maxn][31],a[maxn]; ll ans; int main(){ //freopen("input.in","r",stdin); scanf("%d%d%d",&n,&l,&r); for(int i=1;i<=n;i++) { scanf("%d",&a[i]); for(int j=0;j<=30;j++) { pre[i][j]=(a[i]>>j)&1; } for(int j=0;j<=30;j++) { pre[i][j]+=pre[i-1][j]; cnt[i][j]=pre[i][j]&1; } for(int j=0;j<=30;j++) { if(i>1) cnt[i][j]+=cnt[i-2][j]; } } for(int i=1;i+l-1<=n;i++) { int L=i+l-1,R=min(n,i+r-1); if((L-i+1)&1) L++; if((R-i+1)&1) R--; if(L>R) continue; for(int j=0;j<=30;j++) { ll k=cnt[R][j]-cnt[max(0,L-2)][j]; if(pre[i-1][j]&1) ans+=1ll*((R-L+2)/2-k)*(1<<j)%mod; else ans+=k*(1<<j)%mod; //cout<<i<<','<<j<<','<<k<<endl; ans%=mod; } //cout<<ans<<endl; } printf("%lld\n",ans); }