AT_abc213_h [ABC213H] Stroll

题目描述

高桥君决定在家附近随意散步。
在散步过程中，高桥君会在 $N$ 个地点（地点 $1$、地点 $2$、$\dots$、地点 $N$）之间来回走动。其中，地点 $1$ 是他的家。
有 $M$ 对地点之间存在道路。对于第 $i$ 对地点 $(a_i, b_i)$，地点 $a_i$ 和地点 $b_i$ 之间有长度为 $d$（$1 \leq d \leq T$）公里的道路各 $p_{i,d}$ 条，这些道路是双向的。

高桥君想知道，从家出发，走 $T$ 公里后回到家的散步路线有多少种。这里，长度为 $T$ 公里的散步路线定义如下：

• 存在一个交替排列地点和道路的序列 $v_0 = 1, e_0, v_1, \dots, e_{k-1}, v_k = 1$，其中 $e_i$（$0 \leq i \leq k-1$）连接 $v_i$ 和 $v_{i+1}$，且所有 $e_i$ 的长度之和为 $T$ 公里。

请你帮高桥君计算满足条件的散步路线数量，并对 $998244353$ 取模输出。注意，当两个路线的序列不同，则认为是不同的路线。

输入格式

输入通过标准输入给出，格式如下：

$N$ $M$ $T$
$a_1$ $b_1$ $p_{1,1}$ $p_{1,2}$ $\ldots$ $p_{1,T}$
$\vdots$
$a_M$ $b_M$ $p_{M,1}$ $p_{M,2}$ $\ldots$ $p_{M,T}$

输出格式

输出满足条件的散步路线数量，对 $998244353$ 取模。

输入输出样例 #1

输入 #1

3 2 2
1 2
1 0
1 3
2 0

输出 #1

5

输入输出样例 #2

输入 #2

3 3 4
1 2
3 0 0 0
1 3
0 1 0 0
2 3
2 0 0 0

输出 #2

130

输入输出样例 #3

输入 #3

2 1 5
1 2
31415 92653 58979 32384 62643

输出 #3

844557977

说明/提示

限制条件

• $2 \leq N \leq 10$
• $1 \leq M \leq \min\left(10, \frac{N(N-1)}{2}\right)$
• $1 \leq T \leq 4 \times 10^4$
• $1 \leq a_i < b_i \leq N$
• 若 $i \neq j$，则 $(a_i, b_i) \neq (a_j, b_j)$
• $0 \leq p_{i,j} < 998244353$

样例解释 1

高桥君家附近有：

• 连接地点 $1$ 和地点 $2$ 的长度为 $1$ 公里的道路 $1$ 条
• 连接地点 $1$ 和地点 $3$ 的长度为 $1$ 公里的道路 $2$ 条

满足条件的路线有：

• 按 $1 \to 2 \to 1$ 顺序的路线有 $1 \times 1 = 1$ 种
• 按 $1 \to 3 \to 1$ 顺序的路线有 $2 \times 2 = 4$ 种

共计 $5$ 种。

样例解释 2

高桥君家附近有：

• 连接地点 $1$ 和地点 $2$ 的长度为 $1$ 公里的道路 $3$ 条
• 连接地点 $1$ 和地点 $3$ 的长度为 $2$ 公里的道路 $1$ 条
• 连接地点 $2$ 和地点 $3$ 的长度为 $1$ 公里的道路 $2$ 条

满足条件的路线，按经过的地点列举如下：

• $1 \to 2 \to 1 \to 2 \to 1$
• $1 \to 2 \to 3 \to 1$
• $1 \to 2 \to 3 \to 2 \to 1$
• $1 \to 3 \to 1$
• $1 \to 3 \to 2 \to 1$

对应的路线数分别为 $81$、$6$、$36$、$1$、$6$ 种。

由 ChatGPT 4.1 翻译