P9223 异或 题解

· · 题解

此篇题解是为补充前两位大佬（均为排名前 200 的超级大犇）的题解。毕竟人家和本蒟不在同一水平，简单说几句就以为我这样的小蒟蒻能一下搞懂找到门路（嘤嘤嘤）。

题目大意

传送门

给你 n 和 m，求 1 到 n 所有的数异或上 1 到 m 所有的数结果相加的总和。

整理一波思路

  1. 暴力计算。直接双环枚举 n 和 m，把每一次异或的值算出来再加。这样的话时间复杂度为 O(Tnm)。由于 n,m\le10^{16}，必炸。
  2. 考虑从异或本身定义出发。只有当 a 和 b 某一二进制位一个为 1 且另一个为 0 时异或值为 1。即当进行到第 now 位，若 n 这边取了一个某位为 1 的数，m 这边要取一个同一位为 0 的数才能使结果产生贡献。不妨设 n 这边有 x 个 now 位为 1，m 这边有 y 个 now 位为 1，那么 n 这边贡献（该位为 1 的数的个数）即可表示为 x\times(m-y)，同理 m 这边的贡献为 y\times(n-x)。now 位为 1 时自身数值为 2^{now}，结果用总贡献乘数值，为 [x\times(m-y)+y\times(n-x)]\times2^{now}。然后找到每一位按这种方案求出贡献，加在一起即可。
  3. 如何找到每一位有几个数为 1？（重点来啦，两位奆佬没细讲）设现在在第 now 位。那么，不考虑高位，第 now 位为 0 的数从 0 到 2^{now}-1，一共 2^{now} 个；而第 now 位为 1 的数从 2^{now} 到 2^{now+1}-1，也是 2^{now} 个。那么我们就可以得出第 now+1 位的数值中第 now 位为 1 的占一半！只要我们算出 n\div2^{now+1} 再乘 2^{now} 不就知道这一位有几个数为 1 了吗？（有的人会问这是不是多此一举，直接用 n\div2 不就得了，但实际上 now 可以取到小于等于 n 的最大偶数次幂，换句话说 2^{now+1} 很有可能超过 n，也就是除法运算时 n 不够除。）如果 n 不是 2 的整数次幂，结果必然产生余数。余数中前 2^{now}-1 是第 now 位为 0（与前文相比排除了 0，即没余数），那么 n\bmod2^{now+1}\le 2^{now}-1 时贡献为 0，反之就减去前 2^{now}-1，贡献为 n\bmod2^{now+1}-(2^{now}-1)。

喜闻乐见的代码时间

为了偷懒，本蒟把 now 定义为了 2^{now}，用 i 来枚举当前的位置，观看时请务必注意。

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int M=998244353;
int t,cnt[33][3];
int times(int x,int y)
{
    return ((x%M)*(y%M))%M;
}
int pl(int x,int y)
{
    return ((x%M+y%M)%M+M)%M;
}
inline int read()
{
    int f=1,k=0;
    char c=getchar();//读入一个字符 
    //非数字 
    while(c<'0'||c>'9')//读到空格后
    {
        if(c=='-')f=-1;//读到负数  
        c=getchar();//两个功能：读取负号后面的数字或者读入空格等。 
    }
    //数字 
    while(c>='0'&&c<='9')
    {
        k=(k<<1)+(k<<3)+(c^48);
        c=getchar();//一位一位读入数字 
    }
    return f*k; 
}
signed main()
{
    t=read();
    while(t--)
    {
        int n=read(),m=read(),ans=0,now=1;
        memset(cnt,0,sizeof(cnt));
        for(register int i=0;(1ll<<i)<=max(n,m);i++)
        {       
            int f=now<<1;
            cnt[i][1]=(now<=n?(now*(n/f)+(n%f+1>=now?(n%f-now+1):0)):0);//1~n第i位几个数值位1 
            cnt[i][2]=(now<=m?(now*(m/f)+(m%f+1>=now?(m%f-now+1):0)):0);//1~m第i位几个数值位1 
            ans=pl(ans,times(now,pl(times(cnt[i][1],(m-cnt[i][2])),times(cnt[i][2],n-cnt[i][1]))));
            now<<=1;
        }
        cout<<ans<<endl;
    }
    return 0;
}

最后提醒大家时刻不要忘记模 998244353！完结撒花！感谢观看！