#bYybttg060707. 1669:S-Nim

1669:S-Nim

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


题目描述

原题来自:HDU 1536

两个人玩游戏,规则如下:

  • nn 堆石子,分别有 a1,a2,,ana_1, a_2, \dots, a_n 颗石头;
  • 每次从一堆石子中取走若干石子,可取的石子数必须是集合 S={s1,s2,,sk}S = \{s_1, s_2, \dots, s_k\} 中的一个;
  • 谁无法操作谁输。

多组数据,对于每组数据,给定集合 SS,然后给出 mm 个局面(每个局面给出石子堆数 nn 和各堆石子数 aia_i),判断每个局面是必胜态(W)还是必败态(L)。


输入格式

输入多组数据,每组数据格式如下:

第一行:第一个整数 kk,如果 k=0k = 0 表示数据结束;否则后面跟着 kk 个整数 s1,s2,,sks_1, s_2, \dots, s_k,表示可取石子数的集合。

第二行:一个整数 mm,表示询问的局面数。

接下来的 mm 行,每行描述一个局面:

  • 第一个整数 nn,表示石子堆数;
  • 接下来 nn 个整数 a1,a2,,ana_1, a_2, \dots, a_n,表示每堆石子的数量。

输出格式

对于每组数据,输出一行长度为 mm 的字符串,其中第 ii 个字符表示第 ii 个局面的胜负情况:

  • W 表示先手必胜(Winning position)
  • L 表示先手必败(Losing position)

样例

样例输入

2 2 5
3
2 5 12
3 2 4 7
4 2 3 7 12
5 1 2 3 4 5
3
2 5 12
3 2 4 7
4 2 3 7 12
0

样例输出

LWW
WWL

样例解释

第一组数据:

  • k=2k=2,可取石子数集合 S={2,5}S=\{2,5\}
  • m=3m=3 个询问。
  1. 第一个局面:n=2n=2,石子数 5,125,12
    计算每堆的 SG 值(根据可取石子数集合 {2,5}\{2,5\}):

    • SG(0)=0
    • SG(1)=0(因为无法取 2 或 5,没有合法移动)
    • SG(2)=mex{SG(0)}=1
    • SG(3)=mex{SG(1)}=1
    • SG(4)=mex{SG(2)}=mex{1}=0(因为只能取 2 或 5,5 大于 4 不能取,只能取 2 到 SG(2)=1)
    • SG(5)=mex{SG(0),SG(3)}=mex{0,1}=2
    • SG(6)=mex{SG(1),SG(4)}=mex{0,0}=1
    • SG(7)=mex{SG(2),SG(5)}=mex{1,2}=0
    • SG(8)=mex{SG(3),SG(6)}=mex{1,1}=0
    • SG(9)=mex{SG(4),SG(7)}=mex{0,0}=1
    • SG(10)=mex{SG(5),SG(8)}=mex{2,0}=1
    • SG(11)=mex{SG(6),SG(9)}=mex{1,1}=0
    • SG(12)=mex{SG(7),SG(10)}=mex{0,1}=2

    局面 1:SG(5)=2, SG(12)=2,异或和 = 2⊕2=0,所以先手必败 → L

  2. 第二个局面:n=3n=3,石子数 2,4,72,4,7
    SG(2)=1, SG(4)=0, SG(7)=0,异或和 = 1⊕0⊕0=1≠0,先手必胜 → W

  3. 第三个局面:n=4n=4,石子数 2,3,7,122,3,7,12
    SG(2)=1, SG(3)=1, SG(7)=0, SG(12)=2,异或和 = 1⊕1⊕0⊕2=2≠0,先手必胜 → W

所以第一组输出 LWW

第二组数据:

  • k=5k=5,可取石子数集合 S={1,2,3,4,5}S=\{1,2,3,4,5\}
  • m=3m=3 个询问。

类似计算 SG 值(实际上可取任意 1~5 个,SG 值循环规律明显),计算各局面异或和:

  1. 石子 5,12 → SG(5)=?, SG(12)=? 计算得异或和非 0 → W
  2. 石子 2,4,7 → 异或和非 0 → W
  3. 石子 2,3,7,12 → 异或和为 0 → L

所以第二组输出 WWL


数据范围

对于全部数据:

  • 0<n,m,k1000 < n,m,k \le 100
  • 0<si,ai1040 < s_i, a_i \le 10^4

时空限制

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

提示
这是 Nim 游戏的限制取法版本(Take-away Game 的多堆版本)。
对于给定的集合 SS,我们可以预处理 00max(ai)\max(a_i) 的 SG 值。
递推公式:

$$SG(x) = \text{mex} \{ SG(x - s) \mid s \in S \text{ 且 } s \le x \}$$

然后对于每个局面,计算所有堆的 SG 值的异或和:

  • 若异或和 ≠ 0,先手必胜(W);
  • 若异或和 = 0,先手必败(L)。