题目链接

迷路

题目描述

windy 在有向图中迷路了。

该有向图有 $n$ 个节点，节点从 $1$ 至 $n$ 编号，windy 从节点 $1$ 出发，他必须恰好在 $t$ 时刻到达节点 $n$。

现在给出该有向图，你能告诉 windy 总共有多少种不同的路径吗？

答案对 $2009$ 取模。

注意：windy 不能在某个节点逗留，且通过某有向边的时间严格为给定的时间。

输入格式

第一行包含两个整数，分别代表 $n$ 和 $t$。

第 $2$ 到第 $(n+1)$ 行，每行一个长度为 $n$ 的字符串，第 $(i+1)$ 行的第 $j$ 个字符 $c_{i,j}$ 是一个数字字符，若为 $0$，则代表节点 $i$ 到节点 $j$ 无边，否则代表节点 $i$ 到节点 $j$ 的边的长度为 $c_{i,j}$。

输出格式

输出一行一个整数代表答案对 $2009$ 取模的结果。

样例 #1

样例输入 #1

2 2
11
00

样例输出 #1

1

样例 #2

样例输入 #2

5 30
12045
07105
47805
12024
12345

样例输出 #2

852

提示

样例输入输出 1 解释

路径为 $1\to 1\to 2$。

数据规模与约定

• 对于 $30\%$ 的数据，保证 $n\le 5$，$t\le 30$。
• 对于 $100\%$ 的数据，保证 $2\le n\le 10$，$1\le t\le 10^9$。

解题思路

矩阵快速幂

由于题目中给出的 $t$ 范围很大，故此题不能直接使用图论或者动态规划的方法。
简易版本
假设先不考虑每条路径间的具体距离，只用 0，1 表示两个结点间边连接的情况，可以使用邻接矩阵表示输入的有向图，该邻接矩阵记为 $A$ 。

在矩阵中，一个存i到j路径数的矩阵自乘k次，a[i][j]表示从i到j走k步的路径数。
证明：$c[i][j]+=a[i][k]\ast b[k][j]$，
枚举一个中间点，用乘法原理，i到j两步的路径数等于i到k一步的路径数乘k到j一步的路径，然后再对于不同的中间点用加法原理，每次都枚举了i能到的所有点，以及能到j的所有点。
即矩阵 $A^x[i][j]$ 的值为结点 $i$ 走到结点 $j$ 经过 $x$ 步的情况数。因此，如果只有 0，1 表示两个结点间边连接的情况，那我们就可以通过矩阵快速幂的方式求解。
实际——带权重
因为边权可能为1～9,如果直接存进矩阵的话，存边权显然是不可取的，表示有边权数条路径，存1好像成了一步就能到。
1、输入的结点不超过 10 个
2、两两结点之间的距离也不超过 10
拆解节点——把一个结点拆成 10 份，通过结点内部分结点的连接来模拟不同结点间的距离。这样，拆完结点后邻接矩阵的大小也不会超过 $100\times 100$ 。

通过拆点操作将距离不为 1 的结点一一转化为只有 0，1 的邻接矩阵后，就可以使用矩阵快速幂求解了。

Code

Python3

由于 Python 语言本身执行效率较低，因此该代码直接提交会超时，完成最大的测试用例时间在 11s 左右。

# -*- coding: utf-8 -*-
# @Author : BYW-yuwei
# @Software: python3.8.6
MOD=2009
n,t=map(int,input().split())spn=n*10
class matrix:def __init__(self):self.m=[[0]*205 for i in range(205)]def __mul__(self,other):res=matrix()for i in range(1,spn+1):for j in range(1,spn+1):for k in range(1,spn+1):res.m[i][j]=(res.m[i][j]+self.m[i][k]*other.m[k][j])%MODreturn resdef check(i:int,j:int):return (i-1)*10+jdef power(x:matrix,n:int):ans=matrix()for i in range(1,spn+1):ans.m[i][i]=1while n:if n&1:ans=ans*xx=x*xn>>=1return ansA=matrix()
for i in range(1,n+1):for j in range(1,10):A.m[check(i,j)][check(i,j+1)]=1dis=[0]+[int(j) for j in input()]for j in range(1,n+1):if dis[j]:A.m[check(i,dis[j])][check(j,1)]=1res=power(A,t)
print(res.m[1][10*n-9])