题解 P3949 【答案错误】

手动模拟即可得到后一半是经过前一半反转得到的。又看到是2的n次方，于是灵机一动，转换成二进制，思路呼之欲出：

只需要把分值x减去1，转化成二进制，统计1的个数，再判断奇偶性即可。

这里科普一下，在体育比赛(二人竞技)时,先发球跟后发球会带来一定的心理影响，为了尽量削弱这种发球先后带来的影响，无聊的数学家们就想出了这种顺序：(0表示甲方发球，1表示乙方发球)

0 1

0 1 1 0

0 1 1 0 1 0 0 1

0 1 1 0 1 0 0 1 1 0 0 1 0 1 1 0

...

这可以当作对这种分配方法的感性理解吧。

这里只贴出核心代码，快读、long long这些自己加。

int main(){
   n=read(),q=read();
   while(q--){
      int a=read()-1,cnt=0;
      for(int i=n;~i;i--)
         if(a>=2的i次幂) cnt++,a-=2的i次幂;
      if(cnt%2) printf("Z\n");
      else printf("X\n");
   }
   return 0;
}