← 返回题目列表

AtCoder · oupc2023_day1_g

G. 无法通行的游戏

中文机器翻译题面 查看原题

配点 : 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. (1 点) N\leq100, M\leq1000
  2. (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的否定。