自动搬运

查看原文

来自洛谷，原作者为

	UniGravity 好菜阿。

搬运于2025-08-24 23:10:21，当前版本为作者最后更新于2025-03-20 16:42:55，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

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

记 $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;
}