Solution P11799 【MX-X9-T3】『GROI-R3』Powerless

· · 题解

提供一种没啥思维难度的做法，理清思路后也并不算难写。

记 k_p 表示 k 二进值下第 p 位。

先考虑如何判断 a_i\neq a_j 的相对大小，假设 a_i,a_j 第一个不同的位在 p。假设有 a_i<a_j，则 k_p=0 时 a_i\oplus k<a_j\oplus k，否则 a_i\oplus k>a_j\oplus k。而其它位的情况并不会对该位造成影响。

考虑对于 x=a_i 找出其作为最小值时的贡献。对 a 从小到大排序，那么发现 x,a_j 第一个不同的位在 p 且 x<a_j 的 j 必定是一段连续区间，可以通过二分找出。然后考虑拆位统计 x 的贡献。假设当前贡献的位为 t，则变成我们需要统计 k_p=1 且 k_t\neq x_t 的 k\in[0,m] 的数量。

记 \operatorname{cnt}(p_1,v_1,p_2,v_2) 表示 k_{p_1}=v_1\wedge k_{p_2}=v_2 的 k 的数量。如果直接对每个 p_1,p_2 都跑一遍数位 dp 就是 O(n\log^3V) 的了，不太牛。但是发现这个式子是可以通过分类讨论和位运算直接算出来的。

假设 v_1=1，类似数位 dp 的思路分成到达 p_1 时是否取到上界。如果没取到则之后的位可以随意取，否则我们再记 \operatorname{cnt1}(p,v,m) 表示 k_p=v 且 k\in[0,m] 的 k 的数量。则发现问题转化为了求上面这个式子。这个式子同样可以通过分类讨论是否取到上界来计算贡献。这里建议自己画图推一下，其实只是有点复杂，并不算难。

这样我们就可以做到 O(1) 求 \operatorname{cnt}(p_1,v_1,p_2,v_2)。那么即可 O(n\log^2V) 求所有 a_i<a_j 的贡献。当然还有 a_i>a_j 的贡献，要求变成了 k_p=1，同样做即可。

最后还要算上与自己相同值的贡献，因此一开始需要对 a 去重并统计每个值出现次数。时间复杂度 O(n\log^2V)。

const int N=200005,P=998244353;
int n,m,a[N],tmp[N],c[N],s[N];
il int findr(int l,int v,int k){
    int r=n,mid,ans=1;
    while(l<=r){
        mid=(l+r)>>1;
        if((a[mid]>>k)==(v>>k))ans=mid,l=mid+1;
        else r=mid-1;
    }
    return ans;
}
il int findl(int r,int v,int k){
    int l=1,mid,ans=n;
    while(l<=r){
        mid=(l+r)>>1;
        if((a[mid]>>k)==(v>>k))ans=mid,r=mid-1;
        else l=mid+1;
    }
    return ans;
}
il int c1(int p,int v,int m){
    int ans=0;
    if(v==1){
        ans=(m>>(p+1))*(1<<p);
        if((m>>p)&1)ans+=m&((1<<p)-1),ans++;
    }else{
        if((m>>p)&1)ans=((m>>(p+1))+1)*(1<<p);
        else ans=(m>>(p+1))*(1<<p),ans+=m&((1<<p)-1),ans++;
    }
    return ans;
}
il int count(int p1,int v1,int p2,int v2){
    if(p1==p2){
        if(v1!=v2)return 0;
        else return c1(p1,v1,m);
    }else if(p2>p1)return count(p2,v2,p1,v1);
    int ans=0;
    if(v1){
        ans=(m>>(p1+1))*(1<<(p1-1));
        if((m>>p1)&1)ans+=c1(p2,v2,m&((1<<p1)-1));
    }else{
        if((m>>p1)&1)ans=((m>>(p1+1))+1)*(1<<(p1-1));
        else{
            ans=(m>>(p1+1))*(1<<(p1-1));
            ans+=c1(p2,v2,m&((1<<p1)-1));
        }
    }
    return ans;
}

signed main(){
    int n1=read();n=0,m=read();tmp[0]=-1;
    forto(i,1,n1)tmp[i]=read();sort(tmp+1,tmp+n1+1);
    forto(i,1,n1)if(tmp[i]==tmp[i-1])c[n]++;else a[++n]=tmp[i],c[n]=1;
    forto(i,1,n)s[i]=s[i-1]+c[i];
    int l,r,ans=0,cnt;
    forto(i,1,n){
        forv(k,31){
            if(!((a[i]>>k)&1)){
                l=findr(i,a[i],k)+1,r=findr(i,a[i],k+1);if(l>r)continue;
                forv(k1,31)ans+=1ll*count(k,0,k1,((a[i]>>k1)&1)^1)*(1ll<<k1)%P*(s[r]-s[l-1])%P*c[i]%P,ans%=P;
            }else{
                l=findl(i,a[i],k+1),r=findl(i,a[i],k)-1;if(l>r)continue;
                forv(k1,31)ans+=1ll*count(k,1,k1,((a[i]>>k1)&1)^1)*(1ll<<k1)%P*(s[r]-s[l-1])%P*c[i]%P,ans%=P;
            }
        }
    }
    ans=2*ans%P;
    forto(i,1,n)forv(k,31)ans=(ans+1ll*c[i]*c[i]%P*c1(k,((a[i]>>k)&1)^1,m)%P*(1<<k)%P)%P;
    printf("%lld\n",ans);
    return 0;
}