思路与算法

按DAG逆拓扑求SG。对点u，把相同颜色的所有出边终点SG异或成一个向量，选择颜色集合得到这些向量的任意子集异或，也就是GF(2)张成空间。用201位线性基求该空间mex：若最低缺失的主元位是b，则mex为2^b。无出边点SG为0。最后所有石子所在点SG异或，非零先手胜。

正确性说明

每颗石子是独立公平子游戏，走一步删掉原石子、按颜色产生的石子组合SG为对应终点的异或。所有颜色子集精确给出线性空间（空集合合法）。高位消元基的0到b-1主元存在时能表示全部小于2^b的数，缺b主元则不能表示2^b，所以mex正确。SG组合定理给整体胜负。

复杂度

令B=201、W为机器字位宽。拓扑和建边O(N+M)，每点初始化B个B位基O(NB²/W)，颜色map合并O(MlogM+MB/W)，线性基消元O(MB²/W)，石子异或O(QB/W)。总空间O(M+NB/W+B²/W+MB/W)，包含按颜色聚合的临时向量；N≤200。

易错点

不能把大SG截断到64位；本批稠密DAG实测出现2^98。相同颜色及重复终点要异或合并，不是按边独立选择；无出边即不能操作，不能因为允许空颜色集合就让终点继续删石子。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    cin >> n >> m;
    vector<vector<pair<int, int>>> g(n);
    vector<int> deg(n);
    while (m--) {
        int a, b, c;
        cin >> a >> b >> c;
        g[--a].push_back({--b, c});
        deg[b]++;
    }
    queue<int> q;
    for (int i = 0; i < n; i++)
        if (!deg[i])
            q.push(i);
    vector<int> ord;
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        ord.push_back(u);
        for (auto e : g[u])
            if (!--deg[e.first])
                q.push(e.first);
    }
    vector<bitset<201>> sg(n);
    for (int j = n - 1; j >= 0; j--) {
        int u = ord[j];
        if (g[u].empty())
            continue;
        map<int, bitset<201>> groups;
        for (auto e : g[u])
            groups[e.second] ^= sg[e.first];
        array<bitset<201>, 201> basis;
        for (auto a : groups) {
            auto v = a.second;
            for (int b = 200; b >= 0; b--)
                if (v[b]) {
                    if (basis[b].none()) {
                        basis[b] = v;
                        break;
                    }
                    v ^= basis[b];
                }
        }
        int b = 0;
        while (b <= 200 && basis[b].any())
            b++;
        if (b <= 200)
            sg[u][b] = 1;
    }
    int stones;
    cin >> stones;
    bitset<201> ans;
    while (stones--) {
        int u;
        cin >> u;
        ans ^= sg[--u];
    }
    cout << (ans.any() ? 1 : 0) << '\n';
}