放石子

GitHub跳转原题关系图返回列表

一图上的组合游戏,石子各自独立,故用 SG 定理;按颜色分组的后继 SG 异或张成 F_2 线性空间,逆拓扑序插入线性基求 mex 得每个点的 SG。

OJ: roj

题目 ID: 1815

难度:提高+/省选-

标签:博弈论SG函数线性基拓扑排序python

创建: 2026-10-08 06:19

更新: 2026-10-08 06:19

形式化题目

给定一张 nn 个点、mm 条边的有向无环图,每条边带一个颜色 cc(边可以有重边、可以有相同颜色)。 图上有 qq 颗石子,第 ii 颗位于点 posipos_i,同一个点可以放多颗。

一次操作:选一个有出边且至少有一颗石子的点 xx,先取走 xx 上的一颗石子, 再选一个颜色集合 SS,对点 xx 的每条颜色属于 SS 的出边,在它的终点上各放一颗石子。

双方轮流操作,无法操作者负(Normal Play)。问先手必胜(输出 1)还是后手必胜(输出 0)。

设 SG(u)SG(u) 为"点 uu 上单独放一颗石子"这个子游戏的 SG 值,则初始局面的 SG 值为

SGtotal=⨁i=1qSG(posi),SG_{total} = \bigoplus_{i=1}^{q} SG(pos_i),

SGtotal≠0SG_{total} \ne 0 时先手必胜。

题意注记。 原题面写的"对于每条满足颜色 e∈Se \in S 的出边 ii"没有写明是谁的出边, 只能理解为点 xx 自己的出边——否则这条规则与"选点 xx"毫无关系,题目不可作答。 公开样例 2 1 / 2 1 1 / 1 / 2 也支持这一读法:SG(1)=0SG(1)=0(汇点)、SG(2)=1SG(2)=1, 总异或 1≠01 \ne 0,输出 1,与样例一致。

正解

思路

朴素做法与瓶颈。 最直接的模型是把石子分布写成一个状态向量 (a1,…,an)(a_1, \dots, a_n), 用记忆化搜索从终态(所有石子都落在出度为 00 的点上)反推 P/N 态。

状态数就已经爆炸:qq 颗石子分配到 nn 个点的方案数是 (q+n−1n−1)\binom{q+n-1}{n-1}, q⩽10000q \leqslant 10000 时是天文数字。而且每个状态的转移分支还要枚举 2k2^k 种颜色集合 (kk 为该点的出边颜色种数)。状态空间与转移分支双重爆炸,这条路线不可行。

关键观察 1:石子之间是独立的。 一步操作只取走某一个点的一颗石子, 再往它的后继上放新石子,整个过程完全不依赖其他石子是否存在、放在哪。 所以 q 颗石子构成 q 个互不干扰的独立子游戏,由 Sprague–Grundy 定理:

SGtotal=⨁i=1qSG(posi).SG_{total} = \bigoplus_{i=1}^{q} SG(pos_i).

问题从"qq 颗石子的联合局面"塌缩成"每个点单独一颗石子的 SG 值",与 qq 无关。

关键观察 2:颜色集合 SS 的选择对应 F2\mathbb{F}_2 上的线性张成。 只考虑点 xx 上有一颗石子的局面。把 xx 的出边按颜色分组,记

hc(x)=⨁(x,y,c)∈ESG(y),h_c(x) = \bigoplus_{(x, y, c) \in E} SG(y),

即颜色 cc 下所有出边终点 SG 值的异或和(同色多条边要逐条异或,不去重、不漏算)。 为什么是异或?因为选了颜色 cc 就同时在这些终点上各放一颗石子,这几个新石子又是彼此 独立的子游戏,局面 SG 值就是它们的异或和;不选 cc 则贡献为 00。

于是选了颜色集合 SS 后到达局面的 SG 值为 ⨁c∈Shc(x)\bigoplus_{c \in S} h_c(x)。 颜色之间"选 / 不选"完全自由,所以 xx 能到达的全部后继 SG 值集合恰为

Tx=span⁡F2{ hc(x) },T_x = \operatorname{span}_{\mathbb{F}_2}\{\, h_c(x) \,\},

一个 F2\mathbb{F}_2(二进制异或意义下)的线性子空间。

关键观察 3:线性基 + mex。 由 SG 定义 SG(x)=mex⁡(Tx)SG(x) = \operatorname{mex}(T_x)。 因为 TxT_x 是线性空间,用"最高位为主元"的线性基消元后有一个漂亮结论:

  • 若位置 0,1,…,k−10, 1, \dots, k-1 全都有主元,则 0∼2k−10 \sim 2^k - 1 全落在 span⁡\operatorname{span} 里。 归纳:主元在 k−1k-1 的基向量形如 2k−1⊕r2^{k-1} \oplus r(r<2k−1r < 2^{k-1} 已在 span 内), 异或一下就把 2k−12^{k-1} 加了进来,而子空间对异或封闭。
  • 若位置 jj 不是主元,则 2j∉span⁡2^j \notin \operatorname{span}:任何基向量子集的异或值, 其最高位恰是所取基向量中最大的主元位,不可能是 jj。

两者合起来就是:mex⁡(Tx)=2j∗\operatorname{mex}(T_x) = 2^{j^*},j∗j^* 是最小的非主元位。 (也就是"找最小线性无关位并置 1",与逐位枚举 v=0,1,2,…v = 0, 1, 2, \dots 试 representability 的结果一致,但不必真的枚举。)

正解步骤。

  1. 对 DAG 做逆拓扑排序(Kahn,初值是原图出度为 00 的点,它们的 SG=0SG = 0)。
  2. 处理点 xx:把出边按颜色分组,算出每个颜色的 hc(x)h_c(x),依次插入线性基。
  3. 找出最小非主元位 j∗j^*,令 SG(x)=2j∗SG(x) = 2^{j^*}。
  4. 把 SG(x)SG(x) 回报给 xx 的所有前驱(即累加到前驱的对应颜色桶里,并递减其剩余出度)。
  5. 最后把全部 qq 颗石子所在点的 SGSG 值异或起来,非 00 输出 1,否则 0。

位宽要多少? SGSG 值恒为 2 的幂。若某点 SG(x)=2kSG(x) = 2^k,说明它的后继里出现了 SG=20,21,…,2k−1SG = 2^0, 2^1, \dots, 2^{k-1} 的点,各至少一条出边;而 SG=2iSG = 2^i 的点自己又至少要 ii 条出边(它的 hch_c 里必须凑出 ii 个线性无关的主元)。于是

m  ⩾  k+∑i=0k−1i  =  k+k(k−1)2  =  k(k+1)2.m \;\geqslant\; k + \sum_{i=0}^{k-1} i \;=\; k + \frac{k(k-1)}{2} \;=\; \frac{k(k+1)}{2}.

m⩽5000m \leqslant 5000 时 k⩽99k \leqslant 99,即 SG<2100SG < 2^{100}。C++ 用 bitset<256>(余量 2.5 倍), Python 用原生大整数,都不需要额外处理高精度。

验证。 公开样例 n=2,m=1n=2, m=1,边 2→12 \to 1 颜色 11,石子一颗在点 22:SG(1)=0SG(1) = 0(汇点), 点 22 只有一个颜色、h1=SG(1)=0h_1 = SG(1) = 0,span={0}=\{0\},SG(2)=mex⁡{0}=1SG(2) = \operatorname{mex}\{0\} = 1。 总异或 1≠01 \ne 0 → 输出 1,与样例一致。

小构造对照。 数据中另有一个手工构造可手算校验:点 11 是汇点,2→12 \to 1(色 1)、 3→23 \to 2(色 2)、4→24 \to 2(色 3)、4→34 \to 3(色 4)。则 SG(1)=0SG(1)=0、SG(2)=mex⁡{0}=1SG(2)=\operatorname{mex}\{0\}=1、 SG(3)=mex⁡{1}=mex⁡{0,1}=2SG(3)=\operatorname{mex}\{1\}=\operatorname{mex}\{0,1\}=2、SG(4)=mex⁡{1,2}=mex⁡{0,1,2,3}=4SG(4)=\operatorname{mex}\{1,2\}=\operatorname{mex}\{0,1,2,3\}=4。 石子 {4,3,1}\{4,3,1\} → 4⊕2⊕0=6≠04 \oplus 2 \oplus 0 = 6 \ne 0 → 1;石子 {4,4,1}\{4,4,1\} → 4⊕4⊕0=04 \oplus 4 \oplus 0 = 0 → 0 (同点两颗石子自动抵消,这也说明重复石子必须逐颗异或、不能去重)。

数据来源说明。 本题素材目录中带有造数据脚本 data.py,说明 data/ 的 10 个测试点是 用 std.cpp 自造的(手工样例 + 边界 + 随机 + 极值构造),并非官方原数据。本题面来自网络重建, 出题意图或与原题存在偏差;其中 problem9/10 专门构造了 SG=299SG = 2^{99} 的顶格位宽, 用来检验高精度/位宽处理。以上结论均以实跑 data/ 的结果为准(见下)。

代码

python
#!/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-08 06:19
# update_at: 2026-10-08 06:19

import sys
from collections import deque
from functools import reduce
from operator import xor

type Adj = list[list[tuple[int, int]]]  # adj[x] = [(终点 y, 颜色 c), ...],同色多条边各占一项
type Preds = list[list[int]]            # preds[y] = [所有出边指向 y 的起点 x]


def grundy(n: int, adj: Adj, preds: Preds) -> list[int]:
    """算出每个点单独摆一颗石子时的 SG 值:逆拓扑序递推,SG(x) = mex(span{h_c})。"""
    rest = [len(adj[x]) for x in range(n + 1)]  # 剩余出度,逆拓扑 Kahn 的出队条件
    sg = [0] * (n + 1)                          # 出度为 0 的点无操作,SG 恒为 0
    que = deque(x for x in range(1, n + 1) if not rest[x])
    while que:
        x = que.popleft()
        if adj[x]:                              # 有出边才需要求 SG
            color_xor = {}                      # 颜色 c -> 该色所有出边终点 SG 的异或和
            for y, c in adj[x]:
                color_xor[c] = color_xor.get(c, 0) ^ sg[y]
            basis = {}                          # 主元所在位 -> 基向量,span{h_c} 的线性基
            for v in color_xor.values():
                b = v.bit_length() - 1
                while b >= 0 and b in basis:
                    v ^= basis[b]               # 消去最高位后继续找主元
                    b = v.bit_length() - 1
                if b >= 0:
                    basis[b] = v
            j = 0                               # mex(span) = 2^(最小的非主元位),SG 恒为 2 的幂
            while j in basis:
                j += 1
            sg[x] = 1 << j
        for y in preds[x]:                      # x 的 SG 已定,回报给所有前驱
            rest[y] -= 1
            if not rest[y]:
                que.append(y)
    return sg


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    n, m = next(data), next(data)

    adj: Adj = [[] for _ in range(n + 1)]
    preds: Preds = [[] for _ in range(n + 1)]
    for _ in range(m):
        s, t, c = next(data), next(data), next(data)
        adj[s].append((t, c))
        preds[t].append(s)

    sg = grundy(n, adj, preds)
    q = next(data)
    stones = [next(data) for _ in range(q)]
    total = reduce(xor, (sg[pos] for pos in stones), 0)  # 局面 SG = 各颗石子 SG 的异或和
    print(1 if total else 0)


if __name__ == "__main__":
    solve()
cpp
/**
 * 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-08 06:19
 * update_at: 2026-10-08 06:19
 *
 * ROJ 1815 「放石子」:SG 定理 + 二进制线性基(逆拓扑序)
 *
 * 石子之间互不影响(一步只动一颗),把 q 颗石子看成 q 个独立子游戏,
 * 答案 = 各石子所在点 SG 值的异或和,非 0 先手胜。
 *
 * 单点 SG:设颜色 c 的所有出边终点 SG 的异或和为 h_c。若一次操作选颜色集合 S,
 * 到达局面的 SG 值恰为 XOR_{c in S} h_c,于是 x 的可达 SG 值集合 = span{h_c}
 * (F_2 上的线性子空间),故 SG(x) = mex(span{h_c})。
 *
 * 用「最高位为主元」的线性基:位置 0..j-1 全为主元 <=> [0, 2^j) 全在 span 内;
 * 而位置 j 非主元 <=> 2^j 不在 span 内。所以 mex(span) = 2^(最小的非主元位)。
 *
 * 位宽:SG 值恒为 2 的幂。若某点 SG = 2^k,则它的后继里必须出现指数 0..k-1 的点,
 * 指数为 i 的后继自己至少要有 i 条出边,再加上 x 自己的 k 条出边,得
 *   m >= k + k(k-1)/2 = k(k+1)/2,
 * m <= 5000 时 k <= 99,故 256 位(bitset)有充足余量。
 */
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int MAXN = 205;   // 点数上限 200
const int MAXM = 5005;  // 边数上限 5000
const int W = 256;      // SG 值的位宽(指数上界 99,此处留足余量)

typedef bitset<W> BS;

struct Edge {   // 一条有向边
    int from, to, col;
};
struct Range {  // 节点 x 的出边在 es 中占据的下标区间 [l, r)
    int l, r;
};
struct Redge {  // 反图上的边:由 to 指回它的前驱 from,用于逆拓扑递减剩余出度
    int from, nxt;
};

Edge es[MAXM];
Range rg[MAXN];
Redge re[MAXM];
int rhead[MAXN], rcnt;
int rest[MAXN];   // 逆拓扑 Kahn 的剩余出度计数
BS sg[MAXN];      // sg[x]:单颗石子放在 x 上时的 SG 值(只有一位为 1,或全 0)
BS basis[W];      // 线性基:basis[b] 的主元(最高位)是 b
char isPivot[W];
int que[MAXN];

bool cmpEdge(const Edge &a, const Edge &b) {  // 按 (起点, 颜色) 排序,让同色出边聚成一段
    if (a.from != b.from) return a.from < b.from;
    return a.col < b.col;
}

int main() {
    ll n, m;
    if (scanf("%lld %lld", &n, &m) != 2) return 0;
    for (int i = 0; i < m; i++) {
        int s, t, c;
        scanf("%d %d %d", &s, &t, &c);
        es[i].from = s;
        es[i].to = t;
        es[i].col = c;
        re[++rcnt].from = s;              // 反图:t 的前驱是 s
        re[rcnt].nxt = rhead[t];
        rhead[t] = rcnt;
    }
    sort(es, es + m, cmpEdge);
    for (int i = 0, p = 0; i <= n; i++) {  // 切出每个点的出边区间
        rg[i].l = p;
        while (p < m && es[p].from == i) p++;
        rg[i].r = p;
    }

    int qh = 0, qt = 0;
    for (int i = 1; i <= n; i++) {
        rest[i] = rg[i].r - rg[i].l;                // 原图出度
        if (rest[i] == 0) que[qt++] = i;            // 出度为 0:无路可走,SG = 0
    }
    while (qh < qt) {
        int x = que[qh++];
        if (rg[x].r > rg[x].l) {                    // 有出边的点才需要求 SG
            for (int b = 0; b < W; b++) isPivot[b] = 0;
            for (int i = rg[x].l; i < rg[x].r;) {
                int c = es[i].col;
                BS h;                               // 颜色 c 下所有出边终点 SG 的异或和
                while (i < rg[x].r && es[i].col == c) {
                    h ^= sg[es[i].to];
                    i++;
                }
                for (int b = W - 1; b >= 0; b--) {  // 把 h 插入线性基
                    if (!h[b]) continue;
                    if (!isPivot[b]) {
                        isPivot[b] = 1;
                        basis[b] = h;
                        break;
                    }
                    h ^= basis[b];
                }
            }
            for (int b = 0; b < W; b++)             // mex(span) = 2^(最小的非主元位)
                if (!isPivot[b]) {
                    sg[x].set(b);
                    break;
                }
        }
        for (int i = rhead[x]; i; i = re[i].nxt) {  // x 的 SG 已定,回报给所有前驱
            int y = re[i].from;
            if (--rest[y] == 0) que[qt++] = y;
        }
    }

    ll qn;
    if (scanf("%lld", &qn) != 1) return 0;
    BS total;
    for (int i = 0; i < qn; i++) {
        int a;
        scanf("%d", &a);
        total ^= sg[a];                             // 局面 SG = 各颗石子 SG 的异或和
    }
    printf("%d\n", total.any() ? 1 : 0);
    return 0;
}

复杂度

  • 时间:逆拓扑排序 O(n+m)O(n + m);每对 (点, 颜色) 至多插入线性基一次, Python 侧用整数位运算,单次插入 O(B)O(B)(B⩽100B \leqslant 100 位); C++ 侧用 bitset<256>,单次插入 O(W/64)=4O(W/64) = 4 个机器字。 总计 O(mlog⁡n+n⋅B)O(m \log n + n \cdot B),n⩽200,m⩽5000n \leqslant 200, m \leqslant 5000 时运算量在 10510^5 量级。 最后汇总石子 O(q)O(q)。
  • 空间:邻接表 / 反图各 O(n+m)O(n + m),SG 值与线性基 O(nB)O(n B)。 C++ 用全局数组,200200 个 bitset<256> 仅约 6.4 KB。

总结

这道题的骨架是两句话:独立子游戏的异或和,以及**"选颜色集合"落在 F2\mathbb{F}_2 的线性张成里**。

第一步(SG 定理)把 qq 颗石子的联合状态切成 qq 个互不干扰的单石子游戏, 状态空间从指数级降到 O(n)O(n) 个点;第二步把"枚举 2k2^k 种颜色集合"这一分支爆炸 变成一次线性基消元,再用"最小非主元位"直接读出 mex⁡\operatorname{mex}。

容易写错的地方有三处:

  1. 同色多条出边必须逐条异或进同一个 hch_c,不能按颜色去重;
  2. 递推顺序必须是逆拓扑序,保证算 SG(x)SG(x) 时后继的 SG 值都已就绪;
  3. 重复石子要逐颗异或(偶数颗自然抵消),不能先去重再算。

另外要注意位宽:SGSG 值可以是 2992^{99} 量级的巨大整数,Python 靠原生大整数天然支持, C++ 必须显式给足位数(本轮取 bitset<256>),否则会静默截断成错误答案。