专栏文章

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

UUniGravity
P11799题解参与者 6已保存评论 5

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
5 条
当前快照
1 份
快照标识符
@mipv83fo
此快照首次捕获于
2025/12/03 18:29
3 个月前
此快照最后确认于
2025/12/03 18:29
3 个月前
查看原文
提供一种没啥思维难度的做法，理清思路后也并不算难写。
记 kpk_p 表示 kk 二进值下第 pp 位。
先考虑如何判断 ai≠aja_i\neq a_j 的相对大小，假设 ai,aja_i,a_j 第一个不同的位在 pp。假设有 ai<aja_i<a_j，则 kp=0k_p=0 时 ai⊕k<aj⊕ka_i\oplus k<a_j\oplus k，否则 ai⊕k>aj⊕ka_i\oplus k>a_j\oplus k。而其它位的情况并不会对该位造成影响。
考虑对于 x=aix=a_i 找出其作为最小值时的贡献。对 aa 从小到大排序，那么发现 x,ajx,a_j 第一个不同的位在 pp 且 x<ajx<a_j 的 jj 必定是一段连续区间，可以通过二分找出。然后考虑拆位统计 xx 的贡献。假设当前贡献的位为 tt，则变成我们需要统计 kp=1k_p=1 且 kt≠xtk_t\neq x_t 的 k∈[0,m]k\in[0,m] 的数量。
记 cnt⁡(p1,v1,p2,v2)\operatorname{cnt}(p_1,v_1,p_2,v_2) 表示 kp1=v1∧kp2=v2k_{p_1}=v_1\wedge k_{p_2}=v_2 的 kk 的数量。如果直接对每个 p1,p2p_1,p_2 都跑一遍数位 dp 就是 O(nlog⁡3V)O(n\log^3V) 的了，不太牛。但是发现这个式子是可以通过分类讨论和位运算直接算出来的。
假设 v1=1v_1=1，类似数位 dp 的思路分成到达 p1p_1 时是否取到上界。如果没取到则之后的位可以随意取，否则我们再记 cnt1⁡(p,v,m)\operatorname{cnt1}(p,v,m) 表示 kp=vk_p=v 且 k∈[0,m]k\in[0,m] 的 kk 的数量。则发现问题转化为了求上面这个式子。这个式子同样可以通过分类讨论是否取到上界来计算贡献。这里建议自己画图推一下，其实只是有点复杂，并不算难。
这样我们就可以做到 O(1)O(1) 求 cnt⁡(p1,v1,p2,v2)\operatorname{cnt}(p_1,v_1,p_2,v_2)。那么即可 O(nlog⁡2V)O(n\log^2V) 求所有 ai<aja_i<a_j 的贡献。当然还有 ai>aja_i>a_j 的贡献，要求变成了 kp=1k_p=1，同样做即可。
最后还要算上与自己相同值的贡献，因此一开始需要对 aa 去重并统计每个值出现次数。时间复杂度 O(nlog⁡2V)O(n\log^2V)。
CPP
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;
}

评论

共 5 条评论，欢迎与作者交流。

正在加载评论...