一图上的组合游戏,石子各自独立,故用 SG 定理;按颜色分组的后继 SG 异或张成 F_2 线性空间,逆拓扑序插入线性基求 mex 得每个点的 SG。
OJ: roj
题目 ID: 1815
难度:提高+/省选-
标签:博弈论SG函数线性基拓扑排序python
创建: 2026-10-08 06:19
更新: 2026-10-08 06:19
形式化题目
给定一张
一次操作:选一个有出边且至少有一颗石子的点
双方轮流操作,无法操作者负(Normal Play)。问先手必胜(输出 1)还是后手必胜(输出 0)。
设
题意注记。 原题面写的"对于每条满足颜色
的出边 "没有写明是谁的出边, 只能理解为点 自己的出边——否则这条规则与"选点 "毫无关系,题目不可作答。 公开样例 2 1 / 2 1 1 / 1 / 2也支持这一读法:(汇点)、 , 总异或 ,输出 1,与样例一致。
正解
思路
朴素做法与瓶颈。 最直接的模型是把石子分布写成一个状态向量
状态数就已经爆炸:
关键观察 1:石子之间是独立的。 一步操作只取走某一个点的一颗石子, 再往它的后继上放新石子,整个过程完全不依赖其他石子是否存在、放在哪。 所以 q 颗石子构成 q 个互不干扰的独立子游戏,由 Sprague–Grundy 定理:
问题从"
关键观察 2:颜色集合
即颜色
于是选了颜色集合
一个
关键观察 3:线性基 + mex。 由 SG 定义
- 若位置
全都有主元,则 全落在 里。 归纳:主元在 的基向量形如 ( 已在 span 内), 异或一下就把 加了进来,而子空间对异或封闭。 - 若位置
不是主元,则 :任何基向量子集的异或值, 其最高位恰是所取基向量中最大的主元位,不可能是 。
两者合起来就是:
正解步骤。
- 对 DAG 做逆拓扑排序(Kahn,初值是原图出度为
的点,它们的 )。 - 处理点
:把出边按颜色分组,算出每个颜色的 ,依次插入线性基。 - 找出最小非主元位
,令 。 - 把
回报给 的所有前驱(即累加到前驱的对应颜色桶里,并递减其剩余出度)。 - 最后把全部
颗石子所在点的 值异或起来,非 输出 1,否则0。
位宽要多少?
bitset<256>(余量 2.5 倍),
Python 用原生大整数,都不需要额外处理高精度。
验证。 公开样例 1,与样例一致。
小构造对照。 数据中另有一个手工构造可手算校验:点 1;石子 0
(同点两颗石子自动抵消,这也说明重复石子必须逐颗异或、不能去重)。
数据来源说明。 本题素材目录中带有造数据脚本
data.py,说明data/的 10 个测试点是 用std.cpp自造的(手工样例 + 边界 + 随机 + 极值构造),并非官方原数据。本题面来自网络重建, 出题意图或与原题存在偏差;其中problem9/10专门构造了的顶格位宽, 用来检验高精度/位宽处理。以上结论均以实跑 data/的结果为准(见下)。
代码
#!/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()/**
* 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;
}复杂度
- 时间:逆拓扑排序
;每对 (点, 颜色) 至多插入线性基一次, Python 侧用整数位运算,单次插入 ( 位); C++ 侧用 bitset<256>,单次插入个机器字。 总计 , 时运算量在 量级。 最后汇总石子 。 - 空间:邻接表 / 反图各
,SG 值与线性基 。 C++ 用全局数组, 个 bitset<256>仅约 6.4 KB。
总结
这道题的骨架是两句话:独立子游戏的异或和,以及**"选颜色集合"落在
第一步(SG 定理)把
容易写错的地方有三处:
- 同色多条出边必须逐条异或进同一个
,不能按颜色去重; - 递推顺序必须是逆拓扑序,保证算
时后继的 SG 值都已就绪; - 重复石子要逐颗异或(偶数颗自然抵消),不能先去重再算。
另外要注意位宽:bitset<256>),否则会静默截断成错误答案。