[ CodeForces 1064 B ] Equations of Mathematical Magic-白红宇

[ CodeForces 1064 B ] Equations of Mathematical Magic

阅读量：6337 次

发布时间：2019-06-22

本文共 1055 字，大约阅读时间需要 3 分钟。

\(\\\)

\(T\) 组询问，每次给出一个 \(a\)，求方程

\[ a-(a\oplus x)-x=0 \]

的方案数。

\(T\le 10^3,a\le 2^{30}\)

\(\\\)

\(Solution\)

我菜又被巨佬 \(Diss\) 了......

考场 \(NC\) 问了爷们半懂不懂的就过了......

移项，得

\[ a=(a\oplus x)+x \]

然后注意到满足这个性质的 \(x\) ，在二进制表示下一定是 \(a\) 的子集。

因为\(a\oplus x\)表示的是两者不交的部分的并集，再加上\(x\)表示的就是两个集合的并再加上 \(x\) 这一集合中 \(a\) 集合不包含的部分。

要是想要这个东西等于 \(a\) ，当且仅当 \(x\) 集合中不在 \(a\) 集合中的部分为空集。

然后就是统计 \(a\) 子集的个数。

显然一开始答案为 \(1\) ，遇到二进制位的一个 \(1\) 就答案个数就会翻倍。

\(\\\)

\(Code\)

#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #define R register#define gc getcharusing namespace std;typedef long long ll;inline ll rd(){ ll x=0; bool f=0; char c=gc(); while(!isdigit(c)){if(c=='-')f=1;c=gc();} while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=gc();} return f?-x:x;}ll x,ans=1;void work(){ ans=1ll; x=rd(); while(x){ if((x&1ll)==1ll) ans<<=1; x>>=1; } printf("%I64d\n",ans);}int main(){ ll t=rd(); while(t--) work(); return 0;}