Description
琉璃手头有一黑一白两本魔法书,一本是《缟玛瑙的不在证明》,另一本是《白色相簿1.5》。传说同时打开这两本书会有奇怪的事情发生。琉璃打开一看,果然非常奇怪:两本书上都各自写着一个正整数(可能他买到盗版了),分别是a和b。试图撕书的汀想借过来看看,但琉璃只告诉了他这俩数加起来的值x和异或起来的值y。汀发现有很多种(a,b)满足琉璃告诉他的信息...你能帮他算出来有多少种吗?
Input
两个用空格隔开的整数x和y。
Output
一个整数,表示有多少种情况。
Sample Input
9 5
Sample Output
4
写了比较详细的代码注释……
(写题解的时候突然发现自己的写法又蠢又啰嗦啊,但写都写了就随意发咯(逃),大家看着玩就好了QAQ
//比赛完葱神提到了异或的一条很重要的性质:异或是不进位加法
//另,ll很重要!!!!!
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<iostream>
#define ll long long
using namespace std;
ll x,y,t,tt,ans,nn;
int cnt,now,p[];
bool f[],fl;
ll read()
{
ll x=,f=;char c=getchar();
while(c<''||c>''){if(c=='-')f=-;c=getchar();}
while(c>=''&&c<=''){x=x*+c-'';c=getchar();}
return x*f;
}
int main()
{
x=read();y=read();t=y;
while(t)//一位一位拆了y
{
if(t&)nn++,f[now]=true;//统计1出现的次数,并将其位置打上标记
else p[++cnt]=now;//记录0出现的位置
t>>=;now++;
}
if(x==y){printf("%lld",((ll)<<nn)-);return ;}
//如果x==y,则说明a+b时没有出现进位的情况;
//此时统计1出现的次数nn,则a和b总共有2^nn个组合;
//其中有2个组合为0和x,不满足题意,减掉之后直接输出结果
while((ll)<<now<x)p[++cnt]=now,now++;//将0的位置补满直到1<<now>x为止
nn=(ll)<<nn;
//y中1的位置上,a和b必然是一个为0,一个为1
//所以在确定y中0的位置上a、b相同位置上的数之后,会增加2^nn个答案
//接下来要确定y中0的对应位置上a、b的数
//枚举y中0的位置p,强制位置p上a、b皆为1,位置<p的位置上a、b皆为0,这是为了防止重复
for(int i=;i<=cnt;i++)
{
t=((ll)<<(p[i]+))+y;//先加上强制a、b位置p[i]上皆为1的值
if(t>x)break;//大于x,直接跳出循环
fl=false;now=;tt=x-t;
if(tt%)continue;
//每一次强制a、b某位置上为1都会同时增加a、b的值,所以差值一定为偶数
//根据差值可以推断出哪个位置上a、b同为1
tt>>=;
while(tt)
{
if((tt&)==)//a、b当前位置上同为0,直接跳过
{
tt>>=;now++;
continue;
}
if(f[now]||now<=p[i]){fl=true;break;}
//如果需要a、b同为1的位置小于等于p[i]或该位置上y==1,不合法,直接跳出循环
tt>>=;now++;
}
if(!fl)ans+=nn;//根据枚举出来的状态直接更新答案
}
printf("%lld",ans);
return ;
}