自动搬运

查看原文

来自洛谷，原作者为

	GavinCayne 绝岭衔延不可攀，我自信步留蹊去。

搬运于2025-08-24 22:46:31，当前版本为作者最后更新于2023-09-03 01:24:52，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

此篇题解是为补充前两位大佬（均为排名前 $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$！完结撒花！感谢观看！