[ CodeForces 1064 B ] Equations of Mathematical Magic

\(\\\)

\(Description\)

\(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<cmath>

#include<cstdio>

#include<cctype>

#include<cstdlib>

#include<cstring>

#include<iostream>

#include<algorithm>

#define R register

#define gc getchar

using 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;

}

巴特西

[ CodeForces 1064 B ] Equations of Mathematical Magic

\(Description\)

\(Solution\)

\(Code\)

最新文章

热门文章