AT_dp_r.Walk

普及+/提高

通过率：0%

AC君温馨提醒

该题目为【atcoder】题库的题目，您提交的代码将被提交至atcoder进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

给定一个有 $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
```
4 2
0 1 0 0
0 0 1 1
0 0 0 1
1 0 0 0
```
输出#1
```
6
```
输入#2
```
3 3
0 1 0
1 0 1
0 0 0
```
输出#2
```
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

输入#4
```
1 1
0
```
输出#4
```
0
```

输入#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 翻译

输入解题思路，AI测评打分。不知道怎么写?

首页