Problem1067--#2126. 「HAOI2015」数组游戏

1067: #2126. 「HAOI2015」数组游戏

Time Limit: 1 Sec  Memory Limit: 256 MB
Submit: 0  Solved: 0
[Submit] [Status] [Web Board] [Creator:]

Description

有一个长度为 NNN 的数组，甲乙两人在上面进行这样一个游戏：首先，数组上有一些格子是白的，有一些是黑的。然后两人轮流进行操作。每次操作选择一个白色的格子，假设它的下标为 xxx 。接着，选择一个大小在 1∼n/x1 \sim n/x1∼n/x 之间的整数 kkk，然后将下标为 xxx、2x2x2x、...、kxkxkx 的格子都进行颜色翻转。不能操作的人输。

现在甲（先手）有一些询问。每次他会给你一个数组的初始状态，你要求出对于这种初始状态他是否有必胜策略。

输入格式

第一行一个整数 NNN，表示数组的长度。
第二行一个整数 KKK ，表示询问的个数。
接下来 2K2K2K 行，每两行表示一次询问。
在这两行中，第一行一个正整数 WWW，表示数组中有多少个格子是白色的，第二行则有 WWW 个 1∼N1 \sim N1∼N 之间的正整数，表示白色格子的对应下标。

输出格式

对于每个询问，若先手必胜输出Yes，否则输出No。答案之间用换行隔开。

样例

样例输入

3
2
2
1 2
2
2 3

样例输出

Yes
No

样例解释

在第一个询问中，甲选择点 111，然后将格子 1×11 \times 11×1 和 2×12 \times 12×1 翻过来即可。第二个询问中，无论甲选择哪个点，都只能翻掉一个格子。乙只需翻掉另一个格子就行了。

数据范围与提示

对于 30%30 \%30% 的数据，N≤20N \leq 20N≤20；
对于 50%50 \%50% 的数据，N≤1000000N \leq 1000000N≤1000000；
对于 70%70 \%70% 的数据，N≤10000000N \leq 10000000N≤10000000；
对于 100%100 \%100% 的数据，N≤1000000000N \leq 1000000000N≤1000000000，K,W≤100K,W \leq 100K,W≤100，不会有格子在同一次询问中多次出现。

Source/Category

 
[Submit] [Status]