Description：

给一个 $n-1$ 次多项式 $f(x)=a_1x^{n-1}+a_2x^{n-2}+\cdots+a_nx^0$ ，把 $[1,2^n]$ 划分成两组使得无论系数取什么值两组的和都相同。多次询问某个数被划分到了哪个集合。

$1\leqslant n\leqslant60,1\leqslant q\leqslant 10^6$

Solution：

发现 $2k+1$ 和 $2k+2$ 一定被划分到了两个不同集合，再手玩 $n=4$ 就会发现这个应该是倍增构造的，最后就会发现答案就是这个数减一在二进制位下一的个数，或者是倒推构造的过程奇数就加一放到对面。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cctype>

#include<cstring>

using namespace std;

inline long long read()

{

	register long long res = 0,f = 1;

	register char c = getchar();

	while(!isdigit(c))

	{

		if(c == '-')f = -1;

		c = getchar();

	}

	while(isdigit(c))

	{

		res = (res << 1) + (res << 3) + c - '0';

		c = getchar();

	}

	return res * f;

}

int n,q;

int main()

{

	scanf("%d%d",&n,&q);

	long long k;

	for(int i = 1;i <= q;++i)

	{

		k = read();

		int cur = n & 1;

		for(int p = 0;p <= n;++p)

		{

			if(k & 1)

			{

				++k;

				cur ^= 1;

			}

			k = k >> 1;

		}

		if(cur == 1)puts("X");

		else puts("Z");

	}

	return 0;

}