#P634. 【HAOI2015】数组游戏
【HAOI2015】数组游戏
【题目描述】
有一个长度为N的数组,甲乙两人在上面进行这样一个游戏:
首先,数组上有一些格子是白的,有一些是黑的。然后两人轮流进行操作。每次操作选择一个白色的格子,假设它的下标为x。接着,选择一个大小在1~n/x之间的整数k,然后将下标为x、2x、...、kx的格子都进行颜色翻转。不能操作的人输。
现在甲(先手)有一些询问。每次他会给你一个数组的初始状态,你要求出对于这种初始状态他是否有必胜策略。
【输入格式】
第一行一个整数N,表示数组的长度。
第二行一个整数K,表示询问的个数。
接下来2*K行,没两行表示一次询问。在这两行中,第一行一个正整数W,表示数组中有多少个格子是白色的,第二行则有W个1~N之间的正整数,表示白色格子的对应下标。
【输出格式】
对于每个询问,若先手必胜输出“Yes”,否则输出“No”(均不带引号)。答案之间用换行隔开。
【样例输入】
3
2
2
1 2
2
2 3
【样例输出】
Yes
No
【提示】
在第一个询问中,甲选择点1,然后将格子11和21翻过来即可。第二个询问中,无论甲选择哪个点,都只能翻掉一个格子。乙只需翻掉另一个格子就行了。
对于30%的数据,N<=20;
对于50%的数据,N<=1000000;
对于70%的数据,N<=10000000;
对于100%的数据,N<=1000000000,K,W<=100,不会有格子在同一次询问中多次出现。