$$ \def\xor{\text{ xor }} \def\mex{\mathrm{mex}} \def\SG{\mathrm{SG}} $$
题目描述
有一个长度为 $n$ 的数组,甲乙两人在上面进行这样一个游戏:首先,数组上有一些格子是白的,有一些是黑的。然后两人轮流进行操作。
每次操作选择一个白色的格子,假设它的下标为 $x$。接着,选择一个大小在 $1\ldots \lfloor \dfrac{n}{x} \rfloor$ 之间的整数 $k$,然后将下标为 $x,2\times x,\ldots ,k\times x$ 的格子都进行颜色翻转。不能操作的人输。
现在甲(先手)有一些询问。每次他会给你一个数组的初始状态,你要求出对于这种初始状态他是否有必胜策略。
输入格式
第一行包含一个整数 $n$,表示数组的长度。
第二行包含一个整数 $k$,表示询问的个数。
接下来 $2\times k$ 行,每两行表示一次询问。
在这两行中,第一行一个正整数 $w$,表示数组中有多少个格子是白色的,第二行则有 $w$ 个 $1$ 到 $n$ 之间的正整数,表示白色格子的对应下标。
输出格式
对于每个询问,输出一行一个字符串,若先手必胜输出 Yes
,否则输出 No
。
输入输出样例 #1
输入 #1
1 |
|
输出 #1
1 |
|
说明/提示
样例输入输出 1 解释
在第一个询问中,甲选择点 $1$,然后将格子 $1\times 1$ 和 $2\times 1$ 翻过来即可。
第二个询问中,无论甲选择哪个点,都只能翻掉一个格子。乙只需翻掉另一个格子就行了。
数据规模与约定
对于 $100%$ 的数据,保证 $1\leq n\leq 10^9$, $1\leq k, w \leq 100$ ,不会有格子在同一次询问中多次出现。
题解
本题的结论与 P2594 [ZJOI2009] 染色游戏 - 洛谷 类似。
终止状态显然是所有的格子都是白色。因此对于每个黑色的格子,我们可以将其视为一个独立的游戏单独考虑。换言之,原游戏可拆分成若干个独立的游戏,每个游戏中只有一个黑色的格子。该结论同样可以用数学归纳法证明。
我们用 $\SG(x)$ 表示仅有一个黑色格子 $x$ 的游戏的 SG 函数。
关于 SG 函数的结论: $$ \forall x_1, x_2. \lfloor \frac{n}{x_1} \rfloor = \lfloor \frac{n}{x_2} \rfloor \Rightarrow \SG(x_1) = \SG(x_2) $$ 如果理解了游戏划分的原理,这一结论是显然正确的。
$\lfloor \frac{n}{x} \rfloor$ 本质上只有 $O(\sqrt{n})$ 个不同的取值,因此我们整除分块的方式对 $O(\sqrt{n})$ 个数求出 SG 值即可。