形式化题目

有 $N$ 堆石子，第 $i$ 堆有 $A_i$ 个；给定递增的取法集合 $\mathcal{B} = \{B_1 < B_2 < \dots < B_M\}$。 两人轮流行动，每次从任意一堆中取走恰好 $B_j$ 个（要求该堆石子数不少于 $B_j$）， 无法行动者负，先手先动。要求：

1. 判定先手是否必胜；
2. 若必胜，给出一个第一步 $(i, t)$（从第 $i$ 堆取 $t$ 个），使先手之后有必胜策略； 多个解时，取 $i$ 最小者，$i$ 仍相同时取 $t$ 最小者。

样例：$N = 4$，$A = (7, 6, 9, 3)$，$\mathcal{B} = \{1, 2\}$，答案为 YES 与 1 1。

正解

思路

朴素做法是把整个局面当成状态做博弈递推：

1lose(状态) = 所有后继状态都不是 lose

状态是 $N$ 元组，规模是 $\prod_i (A_i + 1)$。以 $N = 10$、$A_i \leqslant 1000$ 计， 这是 $1001^{10}$ 量级，即便只递推一层也远超任何限制。瓶颈很明确：各堆之间互不干扰， 乘积状态里绝大多数信息是冗余的——第 3 堆取了多少，完全不影响第 7 堆还剩多少种玩法。

这个"一步只改动一堆、双方可用动作集合相同、走不动者负"的结构，正是 不偏组合博弈（Impartial Game）的标准形态，可以直接套 Sprague–Grundy 定理。

先解决一堆的情况。定义单堆 SG 值：

其中 $\operatorname{mex}$ 是"最小的不属于该集合的非负整数"。含义是：$g(x) = 0$ 表示 $x$ 个石子的单堆是必败局面，$g(x) = k > 0$ 表示从这里能走到所有 $g$ 值为 $0..k-1$ 的局面。

以样例的 $\mathcal{B} = \{1,2\}$ 为例，递推结果是 $g(x) = x \bmod 3$：

读表要点：$g(3)$ 可达 $g(2)=2$、$g(1)=1$，集合 $\{1,2\}$，最小缺失值是 $0$，故 $g(3)=0$； $g(1)$ 可达 $g(0)=0$，最小缺失值是 $1$；$g(0)$ 无路可走，按定义取 $0$。

多堆合并用 SG 定理：整个局面的 SG 值等于各堆 SG 的异或和

$S = 0$ 时先手必败（输出 NO），$S \neq 0$ 时先手必胜。样例中 $g(7)=1,\ g(6)=0,\ g(9)=0,\ g(3)=0$，故 $S = 1 \neq 0$，先手必胜。

找第一步：设从第 $i$ 堆取走 $t$ 个。走完后只有第 $i$ 堆的 SG 从 $g(A_i)$ 变成 $g(A_i - t)$，其余各堆在异或式里出现两次、自动抵消，于是新异或和为

要让它变成 $0$（把必败局面留给对手），整理得

右端记作 $T_i$。于是一步制胜的充要条件是：$t \in \mathcal{B}$、$t \leqslant A_i$、 且 $g(A_i - t) = T_i$。

样例中第 1 堆 $A_1 = 7$，$T_1 = 1 \oplus 1 = 0$，需要 $g(7-t) = 0$，即 $7 - t \equiv 0 \pmod 3$， 取法里最小可行的是 $t = 1$（$7-1=6$，$g(6)=0$ ✓），所以输出 1 1； 这也正是样例给出的答案，事后四堆变成 $6,6,9,3$，异或和 $0 \oplus 0 \oplus 0 \oplus 0 = 0$， 对手面对必败局面。

多解的取舍：题目要求"堆编号最小，其次取走个数最小"，恰好就是按 $i$ 从 $1$ 到 $N$、 $t$ 在递增的 $\mathcal{B}$ 上从小到大扫描时遇到的第一个可行解，不需要排序或比较。

代码

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#!/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-10-01 00:58
# update_at: 2026-10-01 00:58

import sys
from functools import reduce
from operator import xor


def sg_table(max_stones: int, moves: list[int]) -> list[int]:
    """算出 0..max_stones 每堆石子的 SG 值：SG(x) 是 x 走一步能到的 SG 里最小的缺失值。"""
    n = max(max_stones + 2, len(moves) + 2)  # SG 值不会超过取法种数，但下标要留够余量
    stamp = [0] * n                          # stamp[v] == x 表示 v 被 x 这一轮占用
    sg = [0] * (max_stones + 1)
    for x in range(1, max_stones + 1):
        for take in moves:
            if take > x:
                break                        # moves 递增，后面的取法都取不动了
            stamp[sg[x - take]] = x          # 拿 x 当时间戳，省掉每轮清零
        while stamp[sg[x]] == x:             # 本轮的 SG 集合里最小的缺失值就是 mex
            sg[x] += 1
    return sg


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    n = next(data)
    heaps = [next(data) for _ in range(n)]
    m = next(data)
    moves = sorted(next(data) for _ in range(m))  # 题面保证递增，这里排序只为不依赖该保证

    sg = sg_table(max(heaps), moves)
    nim = reduce(xor, map(sg.__getitem__, heaps), 0)  # 游戏是 N 堆独立子游戏，整体 SG 就是异或和

    # 一步后要让整体异或和变成 0：第 i 堆必须从 sg[a] 落到 nim ^ sg[a]
    first = next(
        (
            (i + 1, take)
            for i, a in enumerate(heaps)
            for take in moves
            if take <= a and sg[a - take] == nim ^ sg[a]
        ),
        None,
    )

    if first is None:
        print("NO")
    else:
        print("YES")
        print(*first)


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

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
66
67
68
69/**
 * 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-01 00:58
 * update_at: 2026-10-06 01:24
 */
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int MAXN = 15;    // 堆数上限 10，留少量余量
const int MAXA = 1005;  // 每堆石子数上限 1000，SG 表按最大石子树开
const int MAXG = 32;    // SG 值不超过取法种数 M<=10，时间戳数组按 SG 值域开

int n, m;
int heap[MAXN];   // heap[i] 表示第 i 堆的石子数
int take[15];     // take[j] 表示第 j 种可以取走的石子数，题面保证递增
int sg[MAXA];     // sg[x] 表示一堆 x 个石子的 SG 值
int stamp[MAXG];  // stamp[v] == x 表示 SG 值 v 在第 x 轮的 mex 集合里出现过，用 x 当时间戳省去每轮清零

// 单堆 SG 递推：sg[x] = mex{ sg[x - take[j]] | take[j] <= x }
void build_sg() {
    int max_stones = 0;
    for (int i = 1; i <= n; i++) {
        if (heap[i] > max_stones) max_stones = heap[i];
    }
    for (int x = 1; x <= max_stones; x++) {
        for (int j = 1; j <= m; j++) {
            if (take[j] > x) break;              // 取法递增，后面的都取不动了
            stamp[sg[x - take[j]]] = x;
        }
        while (stamp[sg[x]] == x) sg[x]++;       // 最小未出现的 SG 值就是 mex
    }
}

int main() {
    ios::sync_with_stdio(false); cin.tie(0);

    cin >> n;
    for (int i = 1; i <= n; i++) cin >> heap[i];
    cin >> m;
    for (int j = 1; j <= m; j++) cin >> take[j];

    build_sg();

    int nim = 0; // 整个局面的 SG 值等于各堆 SG 的异或和
    for (int i = 1; i <= n; i++) nim ^= sg[heap[i]];

    if (nim == 0) {
        cout << "NO\n";                          // 异或和为 0，先手必败
        return 0;
    }
    cout << "YES\n";

    // 取第 i 堆 t 个后异或和变为 0，等价于 sg[heap[i]-t] == nim ^ sg[heap[i]]；
    // 按 i 从小到大、t 从小到大扫描，第一个可行解即题面要求的字典序最小解。
    for (int i = 1; i <= n; i++) {
        int target = nim ^ sg[heap[i]];
        for (int j = 1; j <= m; j++) {
            if (take[j] > heap[i]) break;
            if (sg[heap[i] - take[j]] == target) {
                cout << i << " " << take[j] << "\n";
                return 0;
            }
        }
    }
    return 0;
}

复杂度

• 时间复杂度：$O(\max A \cdot M + N \cdot M)$。SG 表逐值递推，每个 $x$ 枚举 $M$ 种取法； 异或和与第一步枚举是 $O(N \cdot M)$。与标准 C++ 正解同阶。
• 空间复杂度：$O(\max A + N)$：SG 表与时间戳数组各 $O(\max A)$，石子堆 $O(N)$。
• 实测：10 组真实数据全部 PASS，单组约 0.017 s、峰值约 14.7 MB， 相对 1000 ms / 128 MB 的限制十分宽裕。

总结

• 本题是不偏组合博弈的标准题：一步只动一堆、双方动作集相同、走不动者负， 满足 SG 定理的全部前提。
• 单堆 SG 用 $\operatorname{mex}$ 递推 $g(x) = \operatorname{mex}\{g(x - B_j) \mid B_j \leqslant x\}$， 把乘积级的状态空间压到 $O(\max A)$ 一维。
• 整体胜负只看异或和 $S = \bigoplus g(A_i)$：$S = 0$ 必败，$S \neq 0$ 必胜。
• 第一步的充要条件是 $g(A_i - t) = S \oplus g(A_i)$；按 $(i, t)$ 字典序扫描第一个可行解， 正好满足题目"堆编号最小、其次取走个数最小"的要求。
• 用 $x$ 本身当时间戳数组的值，可以在不牺牲正确性的前提下省掉 mex 每轮的整表清零。