【小奇模拟赛】[bzoj3576]小奇的博弈2

2016年5月21日8020

【题目背景】

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

【问题描述】

给定一个数字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,记忆化搜索会快一些