AT_oupc2023_day1_g Impassable Game

给定一个有 $N$ 个顶点、$M$ 条边的有向图 $G$ 以及一个正整数 $K$。 在 $G$ 中，顶点和边分别编号为顶点 $1$、顶点 $2$、...、顶点 $N$ 以及边 $1$、边 $2$、...、边 $M$。第 $i$ 条边（$1 \leq i \leq M$）是从顶点 $u_i$ 指向顶点 $v_i$ 的边，附加有参数 $b_i$，其中 $b_i$ 为 $0$ 或 $1$。 有向图 $G$ 满足以下三个条件： - $G$ 不包含重边。 - $G$ 不包含环。 - 每个顶点都能通过若干条边从顶点 $1$ 出发到达，且顶点 $1$ 到每个顶点的最短路径长度与最长路径长度相等，且均不超过 $K$。 两名玩家使用各自的一枚棋子进行如下博弈： - 一开始，每位玩家都将自己的棋子放置在顶点 $1$ 上。 - 在自己的回合，玩家可以进行以下两种操作之一： - 移动：将自己的棋子恰好移动一次。若己方棋子处于顶点 $i$，则只能将其移动到有边指向的顶点 $j$ 上。当己方棋子在顶点 $1$ 时，必须等概率且随机地选择一条可以到达的边移动。注意，先手玩家可以使用所有边，后手玩家只能使用 $b_i=0$ 的边。 - 宣布失败：主动认输，结束游戏，本方负，对方胜。 - 由先手玩家开始，双方轮流操作。如果无人宣布失败，在后手玩家完成第 $K$ 次移动操作后，游戏结束。此时，如果两枚棋子位于同一顶点，则后手获胜，否则先手获胜。 每位玩家都以胜利为目标采取最优策略。 请计算先手玩家获胜的概率 $\bmod\ 998244353$。 概率 $\bmod\ 998244353$ 的定义如下：可以证明本题要求的概率一定是有理数，并且在本题的限制下，若该概率为既约分数 $\frac{y}{x}$，则 $x$ 一定与 $998244353$ 互质。此时，存在唯一的 $0 \leq z < 998244353$ 满足 $y \equiv xz \pmod{998244353}$，请输出 $z$。

输入从标准输入读入，格式如下： > $N$ $M$ $K$ $u_1$ $v_1$ $b_1$ $u_2$ $v_2$ $b_2$ $\vdots$ $u_M$ $v_M$ $b_M$

输出先手玩家获胜的概率 $\bmod\ 998244353$。

## 小题点 1.（$1$ 分）$N\leq 100$，$M\leq 1000$ 2.（$99$ 分）无附加限制 ## 样例解释 1 每位玩家各自移动棋子一次后，记先手所在顶点为 $i$，后手所在顶点为 $j$，所有可能的 $(i,j)$ 组合中，先手胜利与后手胜利的组合分别如下： - 先手胜利：$(2,3)$、$(3,3)$ - 后手胜利：$(2,2)$、$(3,2)$ 如当选择到 $(3,2)$ 时，游戏进程可能如下： - 首先将棋子放在顶点 $1$。 - 先手使用边 $2$ 将棋子移到顶点 $3$。 - 后手使用边 $1$ 将棋子移到顶点 $2$。 - 先手使用边 $6$ 将棋子移到顶点 $5$。 - 后手使用边 $4$ 将棋子移到顶点 $5$。 - 后手完成第 $2$ 次移动，游戏结束。两枚棋子都在顶点 $5$，后手胜利。 此外，在 $ (3,2)$ 情况下，无论先手采取何种策略，后手都能获胜。 故先手胜率为 $\frac{1}{2}$，模 $998244353$ 取值为 $499122177$。 此样例满足小题 $1$ 的限制。 ## 样例解释 2 每位玩家各自移动棋子一次后，记先手所在顶点为 $i$，后手所在顶点为 $j$，所有可能的 $(i,j)$ 组合中，先手胜利与后手胜利的组合分别如下： - 先手胜利：$(2,3)$、$(3,2)$、$(3,3)$ - 后手胜利：$(2,2)$ 如当选择到 $(3,2)$ 时，游戏进程可能如下： - 首先将棋子放在顶点 $1$。 - 先手使用边 $2$ 将棋子移到顶点 $3$。 - 后手使用边 $1$ 将棋子移到顶点 $2$。 - 先手使用边 $5$ 将棋子移到顶点 $5$。 - 后手使用边 $3$ 将棋子移到顶点 $4$。 - 后手完成第 $2$ 次移动，游戏结束。此时两枚棋子位于不同顶点，先手胜利。 此外，在 $ (3,2)$ 情况下，无论后手采取何种策略，先手都能获胜。 先手胜率为 $\frac{3}{4}$，模 $998244353$ 取值为 $249561089$。 此样例满足小题 $1$ 的限制。 ## 样例解释 3 后手必须在未进行任何移动时宣布失败。 此样例满足小题 $1$ 的限制。 ## 样例解释 4 此样例满足小题 $1$ 的限制。 # 数据范围 - $2 \leq N \leq 4000$ - $1 \leq M \leq 2 \times 10^{6}$ - $1 \leq K \leq 4000$ - $1 \leq u_i, v_i \leq N$ - $b_i \in \{0, 1\}$ - $G$ 不含重边。 - $G$ 不含环。 - 每个顶点都能通过若干条边从顶点 $1$ 出发到达，且顶点 $1$ 到每个顶点的最短路径长度与最长路径长度相等，且均不超过 $K$。 - 所有输入均为整数。 由 ChatGPT 5 翻译