@zzzc18 2017-09-02T12:14:42.000000Z 字数 3616 阅读 1224

# bzoj4017 小Q的无敌异或

bzoj BIT

$1 \leq N \leq 10^5,元素 0 \leq A_i \leq 10^6$

## Solution

ps: $\quad$ $a\ mod \ 2^{k+1}$ 等价于 $a \ \& \ (2^{k+1}-1)$ //二进制考虑一下

#### First Code(奇偶性):

#include<cstdio>#include<cstring>#include<algorithm>#define LL long long#define MAXN 100010#define MOD 998244353using namespace std;LL n;LL sum[MAXN];LL xsum[MAXN];LL p[MAXN];LL ans;bool tree[MAXN];int lowbit(int x){    return (x)&(-x);}void change(LL pos){    pos++;    if(pos==0)        return;    LL i;    for(i=pos;i<=n+1;i+=lowbit(i))        tree[i]^=1;}LL getnum(LL pos){    LL re=0;LL i;    pos++;    for(i=pos;i;i-=lowbit(i))        re^=tree[i];    return re;}LL getloc(LL x){    LL l=0,r=n;    LL ans=-1;    while(l<=r){        LL mid=(l+r)>>1;        if(p[mid]<=x){            l=mid+1;            ans=mid;        }        else            r=mid-1;    }    return ans;}void solve1(){    LL k;    LL i;    LL cnt[2];    for(k=0;k<=30;k++){        cnt[0]=cnt[1]=0;        LL tmp=0;        for(i=0;i<=n;i++){            bool tt=xsum[i]&(1<<k);            tmp+=cnt[tt^1];            cnt[tt]++;        }        ans += (1<<k) * tmp%MOD;        ans%=MOD;    }    printf("%lld ",ans);}void solve2(){    ans=0;    LL i,k;    for(k = 0;(1LL << k) <= sum[n];k++){        LL tmp=0;        for(i=0;i<=n;i++)            p[i] = sum[i] & ((1LL << (k+1)) - 1);        sort(p,p+n+1);        memset(tree,0,sizeof(tree));        for(i=0;i<=n;i++){            LL now = sum[i] & ((1LL << (k + 1)) - 1);            //printf("%lld %lld\n",now,getloc(now));            LL t1=getnum(getloc(now-(1LL<<k)));            LL t2=getnum(getloc(now+(1LL<<k)));            LL t3=getnum(getloc(now));            change(getloc(now));            //printf("--%lld %lld %lld\n",now-(1LL<<k),now+(1LL<<k),now);            //printf("::%lld %lld %lld\n",t1,t2,t3);            tmp^=t1^t2^t3;        }        if(tmp)            ans |= (1LL<<k);    }    printf("%lld\n",ans);}int main(){    scanf("%lld",&n);    LL i;    LL x;    for(i=1;i<=n;i++){        scanf("%lld",&x);        xsum[i]=xsum[i-1]^x;        sum[i]=sum[i-1]+x;    }    solve1();    solve2();    return 0;}

#### Second Code(统计个数):

#include<cstdio>#include<cstring>#include<algorithm>#define LL long long#define MAXN 100010#define MOD 998244353using namespace std;LL n;LL sum[MAXN];LL xsum[MAXN];LL p[MAXN];LL ans;int tree[MAXN];int lowbit(int x){    return (x)&(-x);}void change(LL pos,int v){    pos++;    if(pos==0)        return;    LL i;    for(i=pos;i<=n+1;i+=lowbit(i))        tree[i]+=v;}LL getnum(LL pos){    LL re=0;LL i;    pos++;    for(i=pos;i;i-=lowbit(i))        re+=tree[i];    return re;}LL getloc(LL x){    LL l=0,r=n;    LL ans=-1;    while(l<=r){        LL mid=(l+r)>>1;        if(p[mid]<=x){            l=mid+1;            ans=mid;        }        else            r=mid-1;    }    return ans;}void solve1(){    LL k;    LL i;    LL cnt[2];    for(k=0;k<=30;k++){        cnt[0]=cnt[1]=0;        LL tmp=0;        for(i=0;i<=n;i++){            bool tt=xsum[i]&(1<<k);            tmp+=cnt[tt^1];            cnt[tt]++;        }        ans += (1<<k) * tmp%MOD;        ans%=MOD;    }    printf("%lld ",ans);}void solve2(){    ans=0;    LL i,k;    for(k = 0;(1LL << k) <= sum[n];k++){        LL tmp=0;        for(i=0;i<=n;i++)            p[i] = sum[i] & ((1LL << (k+1)) - 1);        sort(p,p+n+1);        memset(tree,0,sizeof(tree));        for(i=0;i<=n;i++){            LL now = sum[i] & ((1LL << (k + 1)) - 1);            change(getloc(now),1);            LL t1=getnum(getloc(now-(1LL<<k)));            LL t2=getnum(getloc(now+(1LL<<k)));            LL t3=getnum(getloc(now));            tmp+=t1+t2-t3;        }        if(tmp%2)            ans |= (1LL<<k);    }    printf("%lld\n",ans);}int main(){    scanf("%lld",&n);    LL i;    LL x;    for(i=1;i<=n;i++){        scanf("%lld",&x);        xsum[i]=xsum[i-1]^x;        sum[i]=sum[i-1]+x;    }    solve1();    solve2();    return 0;}

• 私有
• 公开
• 删除