102137: [AtCoder]ABC213 H - Stroll

Memory Limit:256 MB Time Limit:2 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

Score : $600$ points

Problem Statement

Takahashi has decided to wander around his house.
During his walk, he will roam between $N$ points called Point $1$, Point $2$, $\dots$, Point $N$, where Point $1$ is his house.
There are $M$ pairs of points connected by roads; let $(a_i, b_i)$ be the $i$-th of these pairs. There are $p_{i, d}$ roads with a length of $d$ $(1 \leq d \leq T)$ kilometers connecting Point $a_i$ and Point $b_i$.

Takahashi wants to know the number of $T$ kilometers courses that begin and end at his house. Here, a $T$ kilometers course is defined as follows.

  • An alternating sequence with points and roads $v_0 = 1, e_0, v_1, \dots,e_{k-1}, v_k = 1$ such that $e_i$ $(0 \leq i \leq k-1)$ connects $v_i$ and $v_{i+1}$, and the total length of $e_i$ is $T$ kilometers.

Help Takahashi by finding the number of such courses modulo $998244353$. Two courses are considered different when they are different as sequences.

Constraints

  • $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 \lt b_i \leq N$
  • $(a_i, b_i) \neq (a_j, b_j)$ if $i \neq j$.
  • $0 \leq p_{i,j} \lt 998244353$

Input

Input is given from Standard Input in the following format:

$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}$

Output

Print the number of desirable courses, modulo $998244353$.


Sample Input 1

3 2 2
1 2
1 0
1 3
2 0

Sample Output 1

5

Around his house, there are:

  • one $1$-kilometer road connecting Point $1$ and Point $2$, and
  • two $1$-kilometer roads connecting Point $1$ and Point $3$.

We have the following five desirable courses:

  • $1 \times 1 = 1$ course that goes Point $1$ $\to$ Point $2$ $\to$ Point $1$, and
  • $2 \times 2 = 4$ courses that goes Point $1$ $\to$ Point $3$ $\to$ Point $1$.

Sample Input 2

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

Sample Output 2

130

Around his house, there are:

  • three $1$-kilometer roads connecting Point $1$ and Point $2$,
  • one $2$-kilometer road connecting Point $1$ and Point $3$, and
  • two $1$-kilometer roads connecting Point $2$ and Point $3$.

The desirable courses can be classified into the following categories, according to the points visited:

  • Point $1$ $\to$ Point $2$ $\to$ Point $1$ $\to$ Point $2$ $\to$ Point $1$,
  • Point $1$ $\to$ Point $2$ $\to$ Point $3$ $\to$ Point $1$,
  • Point $1$ $\to$ Point $2$ $\to$ Point $3$ $\to$ Point $2$ $\to$ Point $1$,
  • Point $1$ $\to$ Point $3$ $\to$ Point $1$, and
  • Point $1$ $\to$ Point $3$ $\to$ Point $2$ $\to$ Point $1$.

We have $81$, $6$, $36$, $1$, and $6$ course(s) of these categories, respectively.


Sample Input 3

2 1 5
1 2
31415 92653 58979 32384 62643

Sample Output 3

844557977

Input

题意翻译

给定一个 $n$ 个点 $m$ 条边的简单无向图, 每条边边权为一个常数项为 $0$ 的 $T$ 次多项式, 定义路径权值为边权之积, 求所有从 $1$ 号点出发最后回到 $1$ 号点的回路的权值的 $T$ 次项系数和.

Output

得分:$600$分

问题描述

高桥同学决定在他的房子周围闲逛。

在他的行走过程中,他会在被称为点$1$、点$2$、$\dots$、点$N$的$N$个点之间游荡,其中点$1$是他的房子。

有$M$对点由道路连接;令$(a_i, b_i)$为第$i$对这样的点。在连接点$a_i$和点$b_i$的道路上有$p_{i, d}$条长度为$d$ $(1 \leq d \leq T)$公里的路。

高桥同学想知道从他的房子出发并结束于他的房子的$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$取模的结果。如果两个路线作为序列不同,则认为它们是不同的。

限制条件

  • $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 \lt b_i \leq N$
  • $(a_i, b_i) \neq (a_j, b_j)$如果$i \neq j$。
  • $0 \leq p_{i,j} \lt 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

3 2 2
1 2
1 0
1 3
2 0

样例输出1

5

在他家周围,有:

  • 一条连接点$1$和点$2$的$1$公里道路,和
  • 两条连接点$1$和点$3$的$1$公里道路。

我们有以下五条符合条件的路线:

  • $1 \times 1 = 1$条路线走点$1$ $\to$ 点$2$ $\to$ 点$1$,和
  • $2 \times 2 = 4$条路线走点$1$ $\to$ 点$3$ $\to$ 点$1$。

样例输入2

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

样例输出2

130

在他家周围,有:

  • 三条连接点$1$和点$2$的$1$公里道路,
  • 一条连接点$1$和点$3$的$2$公里道路,和
  • 两条连接点$2$和点$3$的$1$公里道路。

符合条件的路线可以根据所经过的点分类如下:

  • 点$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$条路线属于这些类别。


样例输入3

2 1 5
1 2
31415 92653 58979 32384 62643

样例输出3

844557977

加入题单

上一题 下一题 算法标签: