zcmimi's blog

查看原题

点击跳转

难点在于第二问

第一问:

二进制拆位后分别统计就可以了

第二问:

枚举每一位,统计答案该位是否为1

设序列前缀和为S

区间[l,r]区间和二进制下第k位为1,那么(S_r-S_{l-1}) \mod 2^{k+1}\ge 2^k

S_{l-1} \mod 2^{k+1} \le (S_r \mod 2^{k+1})-2^kS_{l-1}\ge 0

S_{l-1} \mod 2^{k+1} \le (S_r\mod 2^{k+1})+2^kS_r<S_{l-1}

离散化后树状数组即可统计

#include<bits/stdc++.h>
const int N=100011,P=998244353;
int n,a[N],s[N],b[21][2],tr[N];
typedef long long ll;
ll S[N],t[N];
void add(int x,int v){
    if(~x)for(int i=x+1;i<=n+1;i+=i&-i)tr[i]^=v;
}
int qry(int x){
    int res=0;
    for(int i=x+1;i;i-=i&-i)res^=tr[i];
    return res;
}
int find(ll x){
    int l=0,r=n,ans=-1;
    while(l<=r){
        int m=l+r>>1;
        if(t[m]<=x)ans=m,l=m+1;
        else r=m-1;
    }
    return ans;
}
int calc(int x){
    ll p=1ll<<x+1;
    t[0]=S[0]=0;
    for(int i=1;i<=n;++i)S[i]=(S[i-1]+a[i])%p,t[i]=S[i];
    std::sort(t,t+n+1);
    memset(tr,0,sizeof tr);
    int ans=0;
    for(int i=0;i<=n;++i){
        add(find(S[i]),1);
        ans^=qry(find(S[i]-(1ll<<x)))^qry(find(S[i]))^qry(find(S[i]+(1ll<<x)));
    }
    return ans;
}
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;++i)scanf("%d",a+i),s[i]=s[i-1]^a[i];
    int ans1=0;ll ans2=0;
    for(int r=0;r<=n;++r)
        for(int i=0;i<=20;++i)
            (ans1+=1ll*(1<<i)*b[i][s[r]>>i&1^1]%P)%=P,
            ++b[i][s[r]>>i&1];
    for(int i=0;i<=40;++i)
        if(calc(i))ans2|=1ll<<i;
    printf("%d %lld\n",ans1,ans2);
}
BZ 4017 小Q的无敌异或
comment评论
Search
search