2016年省赛 G Triple Nim

2016年省赛 G Triple Nim
nim游戏，要求开始局面为先手必败，也就是异或和为0。
如果n为奇数，二进制下最后一位只有两种可能1，1，1和1，0，0，显然异或和为1，所以方案数为0
如果n为偶数，举个例子，14，二进制为1110，我们按位来拆
1110==1000+100+10
1000=100+100+000也就是上一位的1可以拆成下一位的两个1和一个0，对于n在二进制下的每一个1都可以拆成3种情况（0都有三个位置可以选），所以为3^x,又因为如果每次0都选在同一个位置，就会出现0的情况，所以-3。然后这3堆的顺序无关，再除6.

 #include<iostream>

 #include<cstdio>

 #include<queue>

 #include<algorithm>

 #include<cmath>

 #include<ctime>

 #include<set>

 #include<map>

 #include<stack>

 #include<cstring>

 #define inf 2147483647

 #define ls rt<<1

 #define rs rt<<1|1

 #define lson ls,nl,mid,l,r

 #define rson rs,mid+1,nr,l,r

 #define N 100010

 #define For(i,a,b) for(long long i=a;i<=b;i++)

 #define p(a) putchar(a)

 #define g() getchar()

 using namespace std;

 long long T;

 long long n;

 long long ans,t;

 void in(long long &x){

     long long y=;

     char c=g();x=;

     while(c<''||c>''){

         if(c=='-')y=-;

         c=g();

     }

     while(c<=''&&c>=''){

         x=(x<<)+(x<<)+c-'';c=g();

     }

     x*=y;

 }

 void o(long long x){

     if(x<){

         p('-');

         x=-x;

     }

     if(x>)o(x/);

     p(x%+'');

 }

 long long ksm(long long a,long long b){

     while(b%==){

         a*=a;

         b>>=;

     }

     long long r=;

     while(b){

         if(b%==)

             r*=a;

         a*=a;

         b>>=;

     }

     return r;

 }

 void clear(){

     t=;

 }

 int main(){

     in(T);

     while(T--){

         clear();

         in(n);

         if(n%==)

             o();

         else{

             while(n){

                 if(n&)

                     t++;

                 n>>=;

             }

             o((ksm(,t)-)/);

         }

         p('\n');

     }

     return ;

 }