配点 : 100 点
問題文
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 ,以下内容 3 有一件事是可以保证的。
- G 没有多个边。
- G 没有周期。
- 每个顶点都是一个顶点 可以通过沿着 1 的边到达它,并且顶点 从 1 开始的最短路径的长度和最长路径的长度相等,即 K 下面。
2 使用两块,2 一名玩家玩游戏。
- 最初,每个玩家将他的棋子移到顶部。 1 。
- 当轮到你时,玩家将执行以下操作之一:
- 移动:准确移动你的棋子 移动 1 次。你的作品在顶部 当处于 i 时,顶点 具有指向 i 到顶点 j 的边的顶点 它只能移动到 j 。但是,如果您的作品位于顶部 1 ,从可以等概率移动的顶点中随机选择。 1 您必须选择一个并移动它。此外,第一个玩家拥有所有边,第二个玩家拥有 只能使用 b_i=0 的边。
- 宣告失败:以你的失败和对手的胜利结束游戏。
- 第一个玩家轮流进行,如果没有宣告失败,则第二个玩家移动。 K 次后游戏立即结束。那时 2 如果两个棋子在同一顶点,则第二个玩家获胜;如果它们位于不同的顶点,则第一个玩家获胜。
每个玩家都采取最优策略来获胜。
第一个玩家获胜的概率是
使用 \bmod 998244353 找到它。
確率 \bmod 998244353 的定义
可以证明,在这个问题中找到的概率总是有理数。此外,在这个问题的约束下,我们正在寻找的概率可以表示为不可约分数。 当表示为 \frac{y}{x} 时 保证不能被 x 是 在 998244353 整除。这时, 由于只有一个y≡xz \pmod {998244353} 小于 0 \leq z < 998244353 ,z 请输出制約
- 2 \leq N \leq 4{,}000
- 1 \leq M \leq 2 \times 10^{6}
- 1 \leq K \leq 4{,}000
- 1 \leq u_i, v_i \leq N
- b_i \in \{0, 1\}
- G 没有多个边。
- G 没有周期。
- 每个顶点都是一个顶点 可以通过沿着 1 的边到达它,并且顶点 从 1 开始的最短路径的长度和最长路径的长度相等,即 K 下面。
- 所有输入均为整数
小課題
- (1 点) N\leq100, M\leq1000
- (99 点)无附加约束 打印第
入力
输入是按以下格式从标准输入给出的。
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
5 6 2 1 2 0 1 3 0 2 4 0 2 5 0 3 4 0 3 5 1
出力例 1
499122177
每个玩家演奏一块。 移动 1 次后,玩家棋子所在的顶点为 i,背面棋子所在的顶点 当 j 时设置 (i, j) 第一个玩家获胜的组和第二个玩家获胜的组如下所示。
- 先走的一组获胜: (2, 3)、(3, 3)
- 最后一步获胜的组: (2, 2)、(3, 2)
这个 4 两对中, 当选择(3, 2) 时,可以进行以下进程。
- 一、顶点 将碎片放在 1 上。
- 第一步是边。 使用 2 将你的棋子移到顶部 移至 3 。
- 第二步是边。 1 将你的棋子移到顶部 移至 2 。
- 第一步是边。 使用 6 将你的棋子移到顶部 移至 5 。
- 第二步是边。 4 将你的棋子移到顶部 移至 5 。
- 第二个移动者移动棋子。 移动 2 次后,游戏结束。2 两块在顶部 由于它存在于 5 中,所以第二个移动者获胜。
游戏还可以通过其他方式进行,但是 如果选择(3, 2) ,则无论第一个玩家使用什么策略,第二个玩家都可以获胜。
第一个玩家获胜的概率是 \frac{1}{2} 可以得到为 表示为 \bmod 998244353 当表示为 499122177 。 对于
此测试用例满足小课题1的否定。
入力例 2
5 5 2 1 2 0 1 3 0 2 4 0 3 4 1 3 5 0
出力例 2
249561089
每个玩家演奏一块。 移动 1 次后,玩家棋子所在的顶点为 i,背面棋子所在的顶点 当 j 时设置 (i, j) 第一个玩家获胜的组和第二个玩家获胜的组如下所示。
- 先走的一组获胜: (2, 3)、(3, 2)、(3, 3)
- 最后一步获胜的组: (2, 2)
这个 4 两对中, 当选择(3, 2) 时,可以进行以下进程。
- 一、顶点 将碎片放在 1 上。
- 第一步是边。 使用 2 将你的棋子移到顶部 移至 3 。
- 第二步是边。 1 将你的棋子移到顶部 移至 2 。
- 第一步是边。 使用 5 将你的棋子移到顶部 移至 5 。
- 第二步是边。 3 将你的棋子移到顶部 移至 4 。
- 第二个移动者移动棋子。 移动 2 次后,游戏结束。2 第一个玩家获胜,因为两个棋子位于不同的顶点。 如果选择
游戏还可以通过其他方式进行,但是 如果选择(3, 2) ,则无论第二个玩家使用什么策略,第一个玩家都可以获胜。
第一个玩家获胜的概率是 \frac{3}{4} 可以得到为 表示为 \bmod 998244353 当表示为 249561089 。 对于
此测试用例满足小课题1的否定。
入力例 3
2 1 1 1 2 1
出力例 3
1
在抽牌时,移动 1 你甚至不必这样做就必须宣告失败。
此测试用例满足小课题1的否定。
入力例 4
16 21 3 1 2 0 1 3 0 2 4 0 2 5 0 3 6 0 3 7 0 4 8 0 4 9 0 5 10 0 5 11 0 1 12 1 1 13 1 12 14 1 12 15 1 13 6 1 13 7 1 14 8 1 14 9 1 15 10 1 15 11 1 1 16 0
出力例 4
199648871
此测试用例满足小课题1的否定。