「题目背景」

小奇和提比开脑洞又发明了新的游戏。

「问题描述」

给定一个数字F，游戏系统产生T组游戏。每组游戏包括n堆糖果，小奇和提比轮流操作。每次操作时，一方将某一堆数量不小于F的糖果分成M堆(M >= 2且每次可以不同），要满足M堆中任意两堆糖果的差值不超过1，且不存在空堆。若一方不能操作，它就输了。

假设提比和小奇都非常机智，小奇先手，请你预测一下游戏的结果。

「输入格式」

第一行有2个整数T，F

接下来T行，每行第一个整数n，以及n个整数，表示本次游戏每堆糖果数量。

「输出格式」

输出T个整数，用空格隔开，1代表小奇胜利，0代表提比胜利。

「样例输入」

4 3

1 1

1 2

1 3

1 5

「样例输出」

0 0 1 1

「数据范围」

对于 5%的数据, T=1, n=1, F≤1, 每堆石子数量≤10;

对于 10%的数据, T≤100, n≤2, F≤1, 每堆石子数量≤10;

对于 15%的数据, T≤100, n≤100, F≤1, 每堆石子数量≤10;

对于 20%的数据, T≤100, n≤100, F≤5, 每堆石子数量≤15;

对于 40%的数据, T≤100, n≤100, F≤1000, 每堆石子数量≤1000;

对于 100%的数据, T≤100, n≤100, F≤100000, 每堆石子数量≤100000。

题解

40%的数据

直接SG函数暴力，再将n堆SG值取异或和

100%的数据

观察我们暴力的做法，对于当前的石子数x，我们枚举分成i堆，得到的值就是

(x % i是奇数? sg[x / i + 1] : 0) ^ (x – x % i是奇数? sg[x / i] : 0)。

而x / i的取值只有根号x个，对于x / i相同的一组i，可以发现当i的奇偶性相同时sg值不变，于是这一组的sg值就能O1处理

复杂度n根号n，记忆化搜索会快一些