1647：迷路

题目描述

Windy 在有向图中迷路了。该有向图有 $N$ 个节点，Windy 从节点 $0$ 出发，他必须恰好在 $T$ 时刻到达节点 $N-1$。

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

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

输入格式

第一行包含两个整数 $N, T$；

接下来有 $N$ 行，每行一个长度为 $N$ 的字符串。第 $i$ 行第 $j$ 列为 0 表示从节点 $i$ 到节点 $j$ 没有边，为 1 到 9 表示从节点 $i$ 到节点 $j$ 需要耗费的时间。

输出格式

包含一个整数，可能的路径数，这个数可能很大，只需输出这个数除以 $2009$ 的余数。

样例

样例输入 #1

2 2
11
00

样例输出 #1

1

样例解释 #1

• $N=2$，节点编号 $0$ 和 $1$，Windy 从 $0$ 出发，恰好在 $T=2$ 时刻到达节点 $1$。
• 邻接矩阵：
  • 第一行：11 表示从节点 $0$ 到 $0$ 有边，耗时 $1$；从节点 $0$ 到 $1$ 有边，耗时 $1$。
  • 第二行：00 表示从节点 $1$ 到 $0$ 和 $1$ 都没有边。
• 要求 $T=2$，从 $0$ 到 $1$ 的路径：
  • $0 \to 0 \to 1$：时间 $1+1=2$，符合。
  • $0 \to 1$：时间 $1$，不符合 $T=2$。
• 只有 $1$ 种路径，输出 $1$。

样例输入 #2

5 30
12045
07105
47805
12024
12345

样例输出 #2

852

数据范围

• 对于 $30\%$ 的数据，满足 $2 \le N \le 5, 1 \le T \le 30$；
• 对于 $100\%$ 的数据，满足 $2 \le N \le 10, 1 \le T \le 10^9$。

时空限制

• 时间限制：1000 ms
• 内存限制：524288 KB

注意：本题是有向图路径计数问题，但边权可能为 $1$ 到 $9$（不为 $0$），且 $T$ 很大。由于 $N$ 很小（最多 $10$），但 $T$ 可达 $10^9$，需要使用矩阵快速幂加速。然而边权不是 $1$，不能直接使用邻接矩阵的 $T$ 次幂。

常用技巧：将每个节点拆成多个状态，表示在某个时间余数下的位置。因为边权最大为 $9$，我们可以将每个节点 $u$ 拆成 $9$ 个状态：$(u, 0), (u, 1), \dots, (u, 8)$，其中 $(u, k)$ 表示当前在节点 $u$，且已经走了 $k$ 个单位时间（即还需要等待 $?$ 才能完成当前边的剩余时间？）。更常用的方法是：将原图转换为边权为 $1$ 的新图，然后对新图做矩阵快速幂。

具体拆点方法：

• 对于原图中一条从 $u$ 到 $v$ 的边，权值为 $w$，我们将其转换为一条路径：从 $u$ 出发，经过 $w-1$ 个中间状态，最后到达 $v$。即：$u \to u_1 \to u_2 \to \dots \to u_{w-1} \to v$，其中 $u_1, u_2, \dots, u_{w-1}$ 是新添加的节点，每条边权值为 $1$。
• 但这样添加的节点数可能很多（最多 $N \times 9$）。由于 $N \le 10$，边权最大 $9$，所以每个节点最多拆成 $9$ 个状态，总节点数不超过 $N \times 9 = 90$。矩阵大小 $90 \times 90$，矩阵快速幂 $O(90^3 \log T)$，计算量约为 $90^3 \approx 729000$，乘以 $\log T \approx 30$，约 $2 \times 10^7$，可以接受。

更简洁的拆点方法（经典）：

• 对每个节点 $u$，我们创建 $9$ 个状态：$u_0, u_1, \dots, u_8$，其中 $u_0$ 表示实际节点 $u$（即已经完成一条边，可以开始新边的状态）。对于边权 $w$ 的边 $u \to v$，我们连接 $u_0 \to v_{w-1}$（因为从 $u$ 出发，需要 $w$ 个单位时间到达 $v$，所以先到达 $v_{w-1}$，然后经过 $w-1$ 步逐步变成 $v_0$）。同时，对于每个 $k \ge 1$，有 $u_k \to u_{k-1}$ 的边（权值为 $1$），表示时间的流逝。
• 这样，新图中所有边的权值都是 $1$，邻接矩阵 $A$ 表示一步转移（单位时间）的可达性。那么 $A^T$ 中的 $(0_0, (N-1)_0)$ 元素就是从起点 $0_0$ 到终点 $(N-1)_0$ 恰好 $T$ 步的路径数。

具体构造：

• 新图节点编号：对于原节点 $i$，其对应的 $9$ 个状态编号为 $i \times 9 + 0, i \times 9 + 1, \dots, i \times 9 + 8$。通常 $i_0$ 对应 $i \times 9$。
• 对于每个原节点 $i$，对于 $k = 1$ 到 $8$，添加边 $(i \times 9 + k, i \times 9 + k - 1)$，表示时间流逝（即状态 $i_k$ 经过 $1$ 单位时间变为 $i_{k-1}$）。
• 对于原图中从 $i$ 到 $j$ 的边，权值为 $w$（$1 \le w \le 9$），添加边 $(i \times 9, j \times 9 + w - 1)$，表示从 $i_0$ 出发，经过 $1$ 单位时间到达 $j_{w-1}$（然后通过时间流逝边逐步变成 $j_0$）。

这样，新图的节点数为 $N \times 9$，边权均为 $1$，邻接矩阵 $A$ 是 $0/1$ 矩阵。然后计算 $A^T$，取 $(start, end)$ 元素即可，其中 $start = 0 \times 9 = 0$，$end = (N-1) \times 9$。

注意：如果 $T=0$，需要特判：当 $0 = N-1$ 时路径数为 $1$，否则为 $0$。但题目 $T \ge 1$，且 $N \ge 2$，起点和终点不同，所以 $T=0$ 不可能到达（除非起点等于终点，但题目起点 $0$，终点 $N-1$，如果 $N=1$ 则 $0=N-1$，但 $N \ge 2$，所以不考虑）。

算法步骤：

1. 读入 $N, T$ 和邻接矩阵（字符串）。
2. 新图节点数 $tot = N \times 9$，初始化 $tot \times tot$ 的矩阵 $A$ 为 $0$。
3. 对于每个原节点 $i$（$0 \le i < N$）：
   • 对于 $k = 1$ 到 $8$，令 $A[i \times 9 + k][i \times 9 + k - 1] = 1$。
4. 对于每个原节点 $i$ 和 $j$，如果原图中 $i$ 到 $j$ 的边权 $w = str[i][j] - '0'$，且 $w > 0$，则令 $A[i \times 9][j \times 9 + w - 1] = 1$。
5. 计算 $B = A^T$（矩阵快速幂，模 $2009$）。
6. 输出 $B[0][(N-1) \times 9]$（即从起点 $0_0$ 到终点 $(N-1)_0$ 的路径数）。

注意模数 $2009$ 不是质数，但矩阵乘法只需取模即可。

由于 $tot \le 90$，矩阵乘法 $O(tot^3)$ 稍大，但 $90^3=729000$，快速幂 $\log T \le 30$，总计算量约 $2 \times 10^7$，在 1 秒内可能较紧，但可以使用一些优化（如循环展开、使用 int 等）。由于 $N \le 10$，$tot \le 90$，实际可能更小。

另一种优化：注意到矩阵 $A$ 是稀疏的，但快速幂需要稠密矩阵乘法。不过 $90$ 的规模可以接受。