Stone

Alice 和 Bob 在玩取石子的游戏。

他们共有 \(N\) 堆石子，第 \(i\) 堆石子有 \(a_{i}\) 个石子。

Alice 和 Bob 轮流取石子， Alice 先取，每一次取石子，当前取石子的人可以任选一堆还没有被取完的石子，从中取出至少 \(1\) 个，至多 \(x\) 个石子。

如果当前取石子的人没有石子堆可选，那么他（她）就输掉了游戏。

他们想知道，如果 Alice 和 Bob 都用最优策略玩游戏的话，谁会胜利。

由于 Alice 和 Bob 还没商量好 \(x\) 取多少，所以对于每个 \(1\) 到 \(N\) 之间的 \(x\)，你都需要告诉他们谁将取得胜利。

对于 \(20\%\) 的数据， \(N\leqslant 8\)

对于 \(50\%\) 的数据， \(N\leqslant 5\times 10^3\)

对于 \(100\%\) 的数据， \(1\leqslant N\leqslant 5\times 10^5,1\leqslant a_{i}\leqslant N\)

首先，当\(a_i< x\)时，就是经典的取石子了

而只有一堆石子的时候，同样非常经典

所以不难得出当\(0={\LARGE\oplus}_{i=1}^Na_i\%(x+1)\)时为必败态

因为我们可以将所有\(a_i\)拆成\(v+(x+1)t\),使得先手无论如何操作，后手总能使之等效于模数的\(Nim\)游戏

这样就变成了计算所有数模某个数的异或和

我们设\(f_{i,j}\)表示值域区间在\([i,i+2^j)\)内的元素减去\(i\)后的异或和

\(g_{i,j}\)表示值域区间在\([i,i+2^j)\)内的元素的元素奇偶性

不难得到\(f_{i,j}=f_{i,j-1}\oplus f_{i+2^{j-1},j-1}\oplus(g_{i+2^{j-1},j-1}*2^{j-1})\)

这样就可以如同\(ST\)表地查询了

时间复杂度\(O(n\log^2n)\)

#include
using namespace std;
# define ll long long
# define read read1()
# define Type template
Type T read1(){
	T t=0;
	char k;
	bool vis=0;
	do (k=getchar())=='-'&&(vis=1);while('0'>k||k>'9');
	while('0'<=k&&k<='9')t=(t<<3)+(t<<1)+(k^'0'),k=getchar();
	return vis?-t:t;
}
# define fre(k) freopen(k".in","r",stdin);freopen(k".out","w",stdout)
# define ll long long
int a[500005],s,v[20][500005],h[20][500005],Log2[500005];
int query(int l,int r){
	int t=0,g=0;
	for(int i;l<=r;)
		if(i=Log2[r-l+1],l+(1<>1]+1;
	for(int i=0;(1<