#bYybttg060704. 1666:取石子游戏

1666:取石子游戏

好的,我将这道题整理为清晰的题面格式,并补充样例解释、数据范围与时空限制:


题目描述

原题来自:BeiJing 2009 WC

小 H 和小 Z 正在玩一个取石子游戏。取石子游戏的规则是这样的:

  • NN 堆石子;
  • 每个人每次可以从任意一堆石子中取出若干个石子;
  • 每次取石子的个数必须是给定的集合 BB 中的数;
  • 谁不能取石子时就会输掉游戏。

小 H 先进行操作,他想问你他是否有必胜策略,如果有,第一步如何取石子(输出从哪堆取、取几个)。


输入格式

第一行为石子的堆数 NN

接下来 NN 行,每行一个数 AiA_i,表示第 ii 堆石子的个数。

接下来一行为每次取石子个数的种类数 MM

接下来 MM 行,每行一个数 BiB_i,表示每次可以取的石子个数。
输入保证这 MM 个数按照递增顺序排列。


输出格式

第一行为 YES 或者 NO,表示小 H 是否有必胜策略。

若结果为 YES,则第二行包含两个数,第一个数表示从哪堆石子取,第二个数表示取多少个石子。
若有多种答案,取第一个数(堆编号)最小的答案;若仍有多种答案,取第二个数(取的个数)最小的答案。


样例

样例输入

4
7
6
9
3
2
1
2

样例输出

YES
1 1

样例解释

石子堆数:N=4N=4,石子数量分别为 7,6,9,37,6,9,3
可取石子数的集合:M=2M=2,可取 1122 个石子。

这是一个 限制取石子的 Nim 游戏(Nim with Restricted Move),可以用 SG 函数 来求解。

首先计算每堆石子的 SG 值:

  • 对于一堆 xx 个石子,每次可取 1122 个:
    • SG(0)=0SG(0)=0
    • SG(1)=mex{SG(0)}=1SG(1)= \text{mex}\{SG(0)\} = 1
    • $SG(2)= \text{mex}\{SG(0), SG(1)\} = \text{mex}\{0,1\}=2$
    • $SG(3)= \text{mex}\{SG(2), SG(1)\} = \text{mex}\{2,1\}=0$
    • $SG(4)= \text{mex}\{SG(3), SG(2)\} = \text{mex}\{0,2\}=1$
    • $SG(5)= \text{mex}\{SG(4), SG(3)\} = \text{mex}\{1,0\}=2$
    • $SG(6)= \text{mex}\{SG(5), SG(4)\} = \text{mex}\{2,1\}=0$
    • $SG(7)= \text{mex}\{SG(6), SG(5)\} = \text{mex}\{0,2\}=1$
    • $SG(8)= \text{mex}\{SG(7), SG(6)\} = \text{mex}\{1,0\}=2$
    • $SG(9)= \text{mex}\{SG(8), SG(7)\} = \text{mex}\{2,1\}=0$

因此:

  • 堆1(7个):SG=1
  • 堆2(6个):SG=0
  • 堆3(9个):SG=0
  • 堆4(3个):SG=0

初始 Nim-sum = 1000=101 \oplus 0 \oplus 0 \oplus 0 = 1 \neq 0,先手必胜。

要找到第一步操作:
我们需要找到一堆石子,将其 SG 值从 sgisg_i 变为 sgiNim-sumsg_i \oplus \text{Nim-sum},并且变化后石子数量减少的量是合法的(即可取集合 BB 中某个数)。
这里 Nim-sum=1,所以我们要找一堆 sgi1<sgisg_i \oplus 1 < sg_i 对应的堆,且该堆减少石子后的 SG 值为 sgi1sg_i \oplus 1

  • 对于堆1(SG=1):11=01 \oplus 1 = 0,所以要从这堆石子中取若干石子,使其 SG 值从 1 变为 0。查表可知:石子数 7(SG=1)→ 变为石子数 6(SG=0),需要取 11 个石子。合法(可取集合中有 1)。
  • 所以第一步:从第 1 堆取 1 个石子。

输出 YES1 1


数据范围

对于全部数据:

  • N10N \le 10
  • Ai1000A_i \le 1000
  • M10M \le 10
  • Bi10B_i \le 10

时空限制

  • 时间:1000 ms1000 \text{ ms}
  • 内存:524288 KB524288 \text{ KB}

提示
这是 有限取子游戏的组合(Take-away Game)的多堆版本。
解题步骤:

  1. 根据可取石子数集合 BB,递推求出 00max(Ai)\max(A_i) 的 SG 值;
  2. 计算初始所有堆 SG 值的异或和 sumsum
  3. sum=0sum=0,输出 NO;否则输出 YES 并找第一步;
  4. 找第一步:枚举每一堆,尝试取 bBb \in B 个石子,若取后该堆石子数合法(非负),且 sgoldsum<sgoldsg_{old} \oplus sum < sg_{old},且取后该堆的 SG 值等于 sgoldsumsg_{old} \oplus sum,则找到一组解。按题意取堆编号最小、取的个数最小的方案。