← 返回题目列表

AtCoder · awc0053_e

E. 魔法之路

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

分数: 466 分

问题陈述

高桥生活在一个由 N 城市。城市编号从 1 to N.

城市之间有多条单向道路,总共有 给出了 M 道路。的 i第路(1 \leq i \leq M) 是一条从城市出发的单向道路 U_i 前往城市 V_i (U_i \neq V_i),并且有一个非负整数 W_i 称其为“神奇价值”。相同的有序对 (U_i, V_i) 不会出现多次。也就是说,对于任何有序的城市对 (u, v) (u \neq v),距城市最多有一条单向路 u 前往城市 v。请注意,从城市出发的道路 u 前往城市 v 和一条来自城市的道路 v 前往城市 u 可以独立存在。当从城市来的一条路 u 前往城市 v 存在,我们将其魔法值表示为 W(u, v).

高桥想从城市出发 1 并到达城市 N 通过精确遍历 K 道路。更准确地说,是一系列 K+1 城市号码 v_0, v_1, \ldots, v_K 满足以下所有条件的称为 路径:

  • v_0 = 1
  • v_K = N
  • 对于所有人 j = 1, 2, \ldots, K,有一条来自城市的道路 v_{j-1} 前往城市 v_j

允许多次访问同一城市或经过同一条道路。穿过城市 N 一路走来(即,有 N 出现在其中 v_1, v_2, \ldots, v_{K-1})也是允许的。

的 总魔法 路径的 一条路径的 v_0, v_1, \ldots, v_K 被定义为幻值的乘积 K 走过的道路。也就是说,

\prod_{j=1}^{K} W(v_{j-1}, v_j)

高桥想要计算每条可能路径的总魔力并找到它们 总和.

由于该值可能非常大,因此除以求余数 998244353。在这里, 998244353 是质数。将答案输出为介于之间的整数 0 和 998244352,包括在内。

约束

  • 2 \leq N \leq 100
  • 0 \leq M \leq N(N-1)
  • 1 \leq K \leq 10^9
  • 1 \leq U_i \leq N
  • 1 \leq V_i \leq N
  • U_i \neq V_i
  • 0 \leq W_i \leq 10^9
  • 相同的有序对 (U_i, V_i) 从未给出多次
  • 所有输入值均为整数

输入

N M K
U_1 V_1 W_1
U_2 V_2 W_2
\vdots
U_M V_M W_M
  • 第一行包含城市数量 N, 道路数量 M,以及要遍历的道路数量 K,用空格分隔。
  • 以下 M 行给出每条道路的信息(如果 M = 0,这部分不存在)。
  • 的 i- 这些行(1 \leq i \leq M) 包含起始城市 U_i, 目的地城市 V_i,以及魔法值 W_i 的 i第条路,以空格分隔。

输出

单行输出到达城市的所有路径的总魔法值(走过的道路的魔法值的乘积)总和的余数 N 来自城市 1 通过精确遍历 K 道路除以 998244353。如果不存在满足条件的路径,则输出 0.


示例输入 1

4 4 2
1 2 2
1 3 3
2 4 5
3 4 4

示例输出 1

22

示例输入 2

3 1 2
1 2 5

示例输出 2

0

示例输入 3

5 8 3
1 2 3
1 3 2
2 3 4
2 4 1
3 4 5
3 5 2
4 5 3
4 2 1

示例输出 3

63

示例输入 4

10 15 1000000000
1 2 100
2 3 200
3 4 300
4 5 400
5 6 500
6 7 600
7 8 700
8 9 800
9 10 900
1 5 10
5 10 20
3 7 50
2 10 1000000000
1 10 999999999
7 10 42

示例输出 4

0

示例输入 5

2 0 1

示例输出 5

0