AT_dp_r Walk

题目描述

给定一个有 $N$ 个顶点的简单有向图 $G$。顶点编号为 $1, 2, \ldots, N$。

对于每一对 $i, j$（$1 \leq i, j \leq N$），是否存在从顶点 $i$ 到顶点 $j$ 的有向边由整数 $a_{i, j}$ 给出。若 $a_{i, j} = 1$，则表示存在从 $i$ 到 $j$ 的有向边；若 $a_{i, j} = 0$，则不存在。

请问在图 $G$ 中，长度为 $K$ 的有向路径共有多少条？请输出答案对 $10^9 + 7$ 取模的结果。注意，可以多次经过同一条边的路径也要计入。

输入格式

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

$N$ $K$ $a_{1,1}$ $\ldots$ $a_{1,N}$ $:$ $a_{N,1}$ $\ldots$ $a_{N,N}$

输出格式

请输出图 $G$ 中长度为 $K$ 的有向路径的总数，对 $10^9 + 7$ 取模。

输入输出样例 #1

输入 #1

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

输出 #1

6

输入输出样例 #2

输入 #2

3 3
0 1 0
1 0 1
0 0 0

输出 #2

3

输入输出样例 #3

输入 #3

6 2
0 0 0 0 0 0
0 0 1 0 0 0
0 0 0 0 0 0
0 0 0 0 1 0
0 0 0 0 0 1
0 0 0 0 0 0

输出 #3

1

输入输出样例 #4

输入 #4

1 1
0

输出 #4

0

输入输出样例 #5

输入 #5

10 1000000000000000000
0 0 1 1 0 0 0 1 1 0
0 0 0 0 0 1 1 1 0 0
0 1 0 0 0 1 0 1 0 1
1 1 1 0 1 1 0 1 1 0
0 1 1 1 0 1 0 1 1 1
0 0 0 1 0 0 1 0 1 0
0 0 0 1 1 0 0 1 0 1
1 0 0 0 1 0 1 0 0 0
0 0 0 0 0 1 0 0 0 0
1 0 1 1 1 0 1 1 1 0

输出 #5

957538352

说明/提示

限制条件

• 所有输入均为整数。
• $1 \leq N \leq 50$
• $1 \leq K \leq 10^{18}$
• $a_{i, j}$ 仅为 $0$ 或 $1$。
• $a_{i, i} = 0$

样例解释 1

图 $G$ 如下所示。

长度为 $2$ 的有向路径共有如下 $6$ 条：

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

样例解释 2

图 $G$ 如下所示。

长度为 $3$ 的有向路径共有如下 $3$ 条：

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

样例解释 3

图 $G$ 如下所示。

长度为 $2$ 的有向路径共有如下 $1$ 条：

• $4 \to 5 \to 6$

样例解释 5

请不要忘记将答案对 $10^9 + 7$ 取模。

由 ChatGPT 4.1 翻译