异或

也许更好的体验
D e s c r i p t i o n \mathcal{Description} Description

给定L,R,求

<center> i = L R x o r i = L R \sum_{i=L}^{R}xor\sum_{i=L}^{R} i=LRxori=LR </center>

答案对1000000007取模
L , R &lt; = 1 0 9 L,R&lt;=10^9 L,R<=109
S o l u t i o n \mathcal{Solution} Solution

对于有异或的题目要记住这点
每个二进制位是独立计算答案的
我们只需知道 [ L , R ] [L,R] [L,R]中所有数在每个位上的情况:有多少 0 0 0多少 1 1 1
只有 1 1 1^ 0 0 0的结果为 1 1 1,统计出每个为上的 1 1 1 0 0 0的个数,用当前位的值乘以 1 1 1的个数再乘以 0 0 0的个数即可
对于每个二进制位上的0和1出现情况
如第 3 3 3
000
001
010
011
100
101
110
111
2 4 2^4 24出现 2 3 2^3 23 0 0 0 1 1 1
不难发现每 2 n + 1 2^{n+1} 2n+1个数在第n位出现 2 n 2^n 2n 0 0 0 1 1 1
由于对数会被异或两次 i^j, j^i,所以计算时要乘以 2 2 2
a n s = ( a n s + 2 z e r o [ i ] o n e [ i ] 2 i ) ans=(ans+2*zero[i]*one[i]*2^i)%mod; ans=(ans+2zero[i]one[i]2i)
0 0 0 1 1 1的计算
用一个简单的容斥即可
对于第n位
R中包含的 2 n + 1 2^{n+1} 2n+1的个数减去L中包含的 2 n + 1 2^{n+1} 2n+1个数加上 R % 2 n + 1 R\%2^{n+1} R%2n+1中的个数减去 L % 2 n + 1 L\%2^{n+1} L%2n+1中的个数
注意计算的起点为 0 0 0,即求的区间是 [ 0 , R ] [ 0 , L 1 ] [0,R]-[0,L-1] [0,R][0,L1]
处理看代码吧

/******************************* Author:Morning_Glory LANG:C++ Created Time:2019年06月10日 星期一 07时59分11秒 *******************************/
#include <cstdio>
#include <fstream>
#include <cstring>
using namespace std;
const int mod = 1000000007;
const int maxn = 55;
int n,T,t,l,r;
long long ans;
long long zero[maxn],one[maxn],mi[maxn];
int main()
{
	scanf("%d",&T);
	mi[0]=1;
	for (int i=1;i<=31;++i)	mi[i]=mi[i-1]<<1;
	while (T--){
		scanf("%d%d",&l,&r);
		memset(one,0,sizeof(one));
		memset(zero,0,sizeof(zero));
		ans=0;
		for (int i=0;mi[i]<=r;++i){
			one[i]=((r+1)/mi[i+1]-l/mi[i+1])*mi[i];//R中包含的2^{n+1}的个数减去L中包含的2^{n+1}个数
			zero[i]=one[i];
			//加上R%2^{n+1}中的个数
			if (r+1>mi[i+1]){
				t=(r+1)%mi[i+1];
				if (t>mi[i])	one[i]+=t-mi[i],zero[i]+=mi[i];
				else	zero[i]+=t;
			}
			else if (r+1<mi[i+1]){
				if (r+1>mi[i])	one[i]+=r+1-mi[i],zero[i]+=mi[i];
				else	zero[i]-=r+1;
			}
			//减去L%2^{n+1}中的个数
			if (l>mi[i+1]){
				t=l%mi[i+1];
				if (t>mi[i])	one[i]-=t-mi[i],zero[i]-=mi[i];
				else	zero[i]-=t;
			}
			else if (l<mi[i+1]){
				if (l>mi[i])	one[i]-=l-mi[i],zero[i]-=mi[i];
				else	zero[i]-=l;
			}
			ans=(ans+2ll*zero[i]*one[i]%mod*mi[i])%mod;
		}
		printf("%lld\n",ans);
	}
	return 0;
}
全部评论

相关推荐

避坑恶心到我了大家好,今天我想跟大家聊聊我在成都千子成智能科技有限公司(以下简称千子成)的求职经历,希望能给大家一些参考。千子成的母公司是“同创主悦”,主要经营各种产品,比如菜刀、POS机、电话卡等等。听起来是不是有点像地推销售公司?没错,就是那种类型的公司。我当时刚毕业,急需一份临时工作,所以在BOSS上看到了千子成的招聘信息。他们承诺无责底薪5000元,还包住宿,这吸引了我。面试的时候,HR也说了同样的话,感觉挺靠谱的。于是,我满怀期待地等待结果。结果出来后,我通过了面试,第二天就收到了试岗通知。试岗的内容就是地推销售,公司划定一个区域,然后你就得见人就问,问店铺、问路人,一直问到他们有意向为止。如果他们有兴趣,你就得摇同事帮忙推动,促进成交。说说一天的工作安排吧。工作时间是从早上8:30到晚上18:30。早上7点有人叫你起床,收拾后去公司,然后唱歌跳舞(销售公司都这样),7:55早课(类似宣誓),8:05同事间联系销售话术,8:15分享销售技巧,8:30经理训话。9:20左右从公司下市场,公交、地铁、自行车自费。到了市场大概10点左右,开始地推工作。中午吃饭时间大约是12:00,公司附近的路边盖饭面馆店自费AA,吃饭时间大约40分钟左右。吃完饭后继续地推工作,没有所谓的固定中午午休时间。下午6点下班后返回公司,不能直接下班,需要与同事交流话术,经理讲话洗脑。正常情况下9点下班。整个上班的一天中,早上到公司就是站着的,到晚上下班前都是站着。每天步数2万步以上。公司员工没有自己的工位,百来号人挤在一个20平方米的空间里听经理洗脑。白天就在市场上奔波,公司的投入成本几乎只有租金和工资,没有中央空调。早上2小时,晚上加班2小时,纯蒸桑拿。没有任何福利,节假日也没有3倍工资之类的。偶尔会有冲的酸梅汤和西瓜什么的。公司的晋升路径也很有意思:新人—组长—领队—主管—副经理—经理。要求是业绩和团队人数,类似传销模式,把人留下来。新人不能加微信、不能吐槽公司、不能有负面情绪、不能谈恋爱、不能说累。在公司没有任何坐的地方,不能依墙而坐。早上吃早饭在公司外面的安全通道,未到上班时间还会让你吃快些不能磨蹭。总之就是想榨干你。复试的时候,带你的师傅会给你营造一个钱多事少离家近的工作氛围,吹嘘工资有多高、还能吹自己毕业于好大学。然后让你早点来公司、无偿加班、抓住你可能不会走的心思进一步压榨你。总之,大家在找工作的时候一定要擦亮眼睛,避免踩坑!———来自网友
qq乃乃好喝到咩噗茶:不要做没有专业门槛的工作
点赞 评论 收藏
分享
不愿透露姓名的神秘牛友
07-08 10:39
一个证都没&nbsp;我能填什么
程序员小白条:别人有,你为什么没有,还是这个道理,社会就是比较,竞争,淘汰,你要安逸,那么就要做好淘汰的准备
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务