「一本通 6.7 练习 4」S-Nim

形式化题目

给定一个正整数集合 $S = \{s_1, s_2, \dots, s_k\}$ 。

现有 $n$ 堆石子，数量分别为 $a_1, a_2, \dots, a_n$ 。两名玩家轮流行动：每次行动选定任意一堆石子（假设当前有 $x$ 颗），并从中移走 $s \in S$ 颗石子（需满足 $s \leqslant x$ ）。无法进行合法操作的玩家判负。

多组测试数据，每组数据给定集合 $S$ 和 $m$ 个独立的初始局面 $(a_1, a_2, \dots, a_n)$ ，要求判定每个局面先手是否必胜（必胜输出 W，必败输出 L）。

正解

思路

本题是典型的公平组合游戏（ICG），由若干堆互相独立的子游戏组成。每个子游戏只在一堆石子上进行，且操作只改变该堆石子的数量，不影响其他堆。

根据 Sprague-Grundy 定理，多个独立子游戏的和等价于各个子游戏 SG 函数值的异或和（XOR sum）。若异或和非 $0$ 则当前局面必胜（W），若异或和为 $0$ 则当前局面必败（L）。

对于单堆大小为 $x$ 的石子堆，其 SG 函数定义为：

\text{SG}(x) = \text{mex}\left(\{\text{SG}(x - s) \mid s \in S, s \leqslant x\}\right)

其中

\text{mex}(T)

表示不属于集合

T

的最小非负整数。基础状态为

\text{SG}(0) = 0

。

因为每组测试数据中集合 $S$ 保持不变，而单堆石子数量上限为 $V = 10^4$ ，我们可以先将 $S$ 升序排序，从 $1$ 到 $V$ 依次递推预处理出所有 $\text{SG}(x)$ 的值。对于每个询问局面，只需查表计算 $\bigoplus_{i=1}^n \text{SG}(a_i)$ 是否为 $0$ 即可。

下面给出转移与 SG 函数计算过程的示意：

graph TD
    subgraph 状态转移与 mex 运算
        X["当前状态 x"]
        N1["后继 x - s1 (SG=0)"]
        N2["后继 x - s2 (SG=1)"]
        N3["后继 x - s3 (SG=3)"]
        X --> N1
        X --> N2
        X --> N3
        MEX["mex({0, 1, 3}) = 2\nSG(x) = 2"]
        N1 -.-> MEX
        N2 -.-> MEX
        N3 -.-> MEX
    end

代码

Python 版：

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-04-18 10:00
# update_at: 2026-04-18 10:00

import sys
from collections.abc import Iterator
from functools import reduce
from operator import xor

MAX_A = 10000  # 石子堆规模上限，每堆石子数不超过 10^4


def compute_sg(moves: list[int], limit: int) -> list[int]:
    """预计算 0 到 limit 的 SG 函数值表。

    状态 x 的后继状态为 {x - s | s in moves, s <= x}，
    SG(x) 为所有后继状态 SG 值的 mex（最小未出现的非负整数）。
    """
    sorted_moves = sorted(moves)
    sg = [0] * (limit + 1)
    tag = [0] * (len(sorted_moves) + 2)

    for x in range(1, limit + 1):
        for s in sorted_moves:
            if s > x:
                break
            v = sg[x - s]
            if v < len(tag):
                tag[v] = x
        mex = 0
        while tag[mex] == x:
            mex += 1
        sg[x] = mex

    return sg


def solve() -> None:
    data: Iterator[int] = iter(map(int, sys.stdin.buffer.read().split()))
    out: list[str] = []

    while True:
        k = next(data, 0)
        if k == 0:
            break

        moves = [next(data) for _ in range(k)]
        sg = compute_sg(moves, MAX_A)

        m = next(data)
        out.append(
            "".join(
                "W" if reduce(xor, (sg[next(data)] for _ in range(next(data))), 0) else "L"
                for _ in range(m)
            )
        )

    print("\n".join(out))


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-06 01:30
 * update_at: 2026-10-06 01:30
 */
#include <cstdio>
#include <algorithm>
typedef long long ll;

const int MAXV = 10000; // 每堆石子数上限 a_i <= 10^4
const int MAXK = 105;

int k, m, n;
int s[MAXK];            // s[i]：每次允许取走的石子数集合
int sg[MAXV + 5];       // sg[x]：单堆石子数为 x 时的 SG 函数值
int tag[MAXK + 5];      // tag[v] = 最近一次出现 SG 值 v 的状态 x（时间戳标记，避免每次清空）

// 预处理 0..MAXV 的 SG 值：SG(x) = mex{ SG(x-s) | s in S, s <= x }
// k 个后继最多 k 个不同 SG 值，所以 mex <= k，tag 数组开 k+5 够用
void precompute() {
    std::sort(s + 1, s + k + 1); // 升序排序，方便提前 break
    for (int x = 1; x <= MAXV; x++) {
        for (int i = 1; i <= k && s[i] <= x; i++) {
            int v = sg[x - s[i]];
            tag[v] = x; // 给 SG 值 v 打上"本轮出现过"的时间戳
        }
        int mex = 0;
        while (tag[mex] == x) mex++; // 找最小的没出现过的非负整数
        sg[x] = mex;
    }
}

int main() {
    while (scanf("%d", &k) == 1 && k != 0) {
        for (int i = 1; i <= k; i++) scanf("%d", &s[i]);
        precompute();

        scanf("%d", &m);
        for (int t = 1; t <= m; t++) {
            scanf("%d", &n);
            int res = 0;
            for (int i = 1; i <= n; i++) {
                int a;
                scanf("%d", &a);
                res ^= sg[a]; // 多堆独立子游戏，SG 定理：异或和判胜负
            }
            if (res != 0) printf("W");
            else printf("L");
        }
        printf("\n");
    }
    return 0;
}

复杂度

时间复杂度：
- 单组数据预处理 SG 值：状态数为 $V = 10^4$ ，转移数为 $|S| = k \leqslant 100$ 。递推预处理耗时 $O(V \cdot k)$ 。
- 单组数据回答 $m$ 个局面：每个局面有 $n$ 堆石子，异或求和耗时 $O(m \cdot n)$ 。
- 总时间复杂度为 $O(T \cdot (V \cdot k + m \cdot n))$ ，在限定时间内能够轻松通过。
空间复杂度：
- 存储 SG 函数表只需 $O(V)$ 大小的数组；时间戳标记数组长度不超过 $k + 2$ 。
- 总空间复杂度为 $O(V)$ ，符合内存限制。

总结

对于每一步可转移状态规则固定的独立子游戏之和：

识别出单堆石子的独立性与有向无环图结构；
利用 $\text{mex}$ 递推预处理单堆的 $\text{SG}$ 值表；
将多堆局面的胜负判定等价转化为各子游戏 $\text{SG}$ 值的异或和判定。

「一本通 6.7 练习 4」S-Nim

目录

形式化题目

正解

思路

代码

复杂度

总结