三校联考20181017T1 异或xor

题意：

题解：
子任务1：直接$O((r-l)^2)$O((r−l)2)暴力即可。
子任务3：我们随便举一个l=0,r=3的例子（为节省篇幅，表只打了一半）。

…
可以发现，枚举每一个i时，i^j都会使[l,r]中的每一个数恰好出现一次，所以就有$\dfrac{r\times (r+1)^2}{2}$2r×(r+1)2​.

子任务2：我们接着可以发现答案是可以按位计算的，对于某一位，令$cnt0$cnt0为这一位上0的个数，$cnt1$cnt1为这一位上1的个数。那么这一位上的结果就是$2\times cnt0\times cnt1$2×cnt0×cnt1。最后答案求和即可。可以枚举$[l,r]$[l,r]间的每一个数，累加每一位上1的个数。

正解：我们接着发现，$[0,x]$[0,x]上每一位的1的个数可以用以下方法来求：令t为最高位，那么第t位上1的个数加上$x-2^t+1$x−2t+1，后面每一位上1的个数加上$2^{t-1}$2t−1，然后递归处理$x-2^t$x−2t。然后$[l,r]$[l,r]上每一位1的个数就是$[0,r]-[0,l-1]$[0,r]−[0,l−1]。

代码：

#include<cstdio>
#include<cstring>
#define mod 1000000007
#define D 32
int t,l,r,sum,cnt[D];
void Getcnt(int x,int d)
{
	if(x<=0) return;
	int t;
	for(t=0;(1<<t)<=x;t++); t--;
	cnt[t]+=d*(x-(1<<t)+1);
	for(int i=0;i<t;i++) cnt[i]+=d*(1<<(t-1));
	Getcnt(x-(1<<t),d);
}
int main()
{
	scanf("%d",&t);
	while(t--)
	{
		sum=0;
		scanf("%d%d",&l,&r);
		memset(cnt,0,sizeof(cnt));
		Getcnt(r,1); Getcnt(l-1,-1);
		for(int i=0;i<D;i++) sum=(sum+2ll*(1<<i)%mod*cnt[i]%mod*(r-l+1-cnt[i])%mod)%mod;
		printf("%d\n",sum);
	}
}