形式化题目

给定一个 $N$ 个节点的有向图。节点 $u$ 到节点 $v$ 的边权由字符 $A[u][v]$ 给出： 字符 0 表示没有边，字符 1 到 9 表示这条边走一次需要耗费这么多时间。 一条走法每经过一条边就把该边的权累加，求满足「从节点 $0$ 出发、总耗时恰好为 $T$、 终点是节点 $N-1$」的走法条数，答案对 $2009$ 取模。

走法（walk）允许重复经过节点和边，例如样例 1 的答案是 $0\to 0\to 1$，重复使用了节点 $0$。 由于每条边的权都是正整数，走法每经过一条边时间必定前进，所以「不能在节点上逗留」 这条限制已经被边权为正自动满足，不需要额外处理。

样例解读

样例 1 输入 2 2 / 11 / 00 表示：节点 $0$ 到节点 $0$ 有一条权为 $1$ 的自环， 节点 $0$ 到节点 $1$ 有一条权为 $1$ 的边（第 1 行 11），节点 $1$ 没有任何出边（第 2 行 00）。 要在恰好 $2$ 个时间单位内从 $0$ 走到 $1$：先走自环再走直边，$0\to0\to1$，总权 $1+1=2$， 只有这一条，因此输出 $1$。第二个样例（$N=5,T=30$）答案为 $852$。

正解

思路

朴素做法。 设 $x_t[v]$ 表示「时刻 $t$ 恰好站在节点 $v$ 上」的走法数，那么

按 $t$ 从 $1$ 推到 $T$ 即可，答案是 $x_T[N-1]$（下标为负的 $x_{t-w}$ 视为 $0$）。 这是 $O(T\cdot 9N^2)$ 的逐时刻递推。 $T\le 30$ 的部分分刚好能过；但当 $T$ 达到 $10^9$ 时，循环次数约 $10^{11}$，时间与 $O(TN)$ 的空间都不可行。瓶颈很清楚：我们在一秒一秒地推进。

观察一：如果所有边权都是 1。 设 $N\times N$ 的 0/1 邻接矩阵为 $M$，由矩阵乘法的 组合意义，$(M^k)[u][v]$ 恰好等于从 $u$ 到 $v$ 走恰好 $k$ 步的走法数。 把状态写成长度为 $N$ 的行向量 $x_k$，递推就是 $x_k=x_{k-1}M$，于是

用矩阵快速幂计算，复杂度降到 $O(N^3\log T)$，与 $T$ 的大小无关。

观察二：边权只有 1 到 9。 这是一个很小的常数，可以让「一条长边占用 $w$ 的时间」 变成「$w$ 条各耗时 1 的边」。具体做法是拆点：把每个原节点 $v$ 换成 9 个状态

其中 $(v,0)$ 表示「真正站在节点 $v$ 上」，$(v,k)$（$k\ge1$）表示「已经踏上了通往 $v$ 的那条边，但还需 $k$ 个单位时间才真正落到 $v$」，即一个「在路上」的中间状态。

于是扩展图 $G'$ 上有两类边：

• 原边：对每个非零字符 $c=A[u][v]$，连边 $(u,0)\longrightarrow(v,c-1)$；
• 等待链：对每个 $v$ 和 $k=1..8$，连边 $(v,k)\longrightarrow(v,k-1)$。

每条扩展边都恰好耗时 1。权为 1 的原边直接落在 $(v,0)$，不产生等待步。

一条权为 3 的长边会摊平成这样（玩具例子）：先花 1 步踏上边，再原地等待 2 步。

1
2
3
4
5(0,0)[1]  --1-->  (1,2)[2]  --1-->  (1,1)[3]  --1-->  (1,0)[4]
  [1] (0,0)：起点，时刻 0 站在 0 上
  [2] (1,2)：第 1 步踏上这条长边，还需 2 步
  [3] (1,1)：再等 1 步，还需 1 步
  [4] (1,0)：真正落到 1，累计用时 3

为什么不会重复计数。 关键在于等待链没有分支：每个 $(v,k)$（$k\ge1$）只有 $(v,k-1)$ 一条出边。所以一条走法一旦踏上权为 $w$ 的边，后面必须连续等待 $w-1$ 步， 别无选择；反过来，扩展图里任何一段 $(u,0)\to(v,w-1)\to\dots\to(v,0)$ 也可以唯一地 压回原图的一条权为 $w$ 的边 $u\xrightarrow{w}v$。两个方向一一对应，计数相等。

得到答案。 扩展图有 $S=9N\le 90$ 个点，边权全为 1。设它的 0/1 邻接矩阵为 $M$ （$S\times S$），行向量 $x_0$ 只在 $(0,0)$ 位置为 $1$，那么

即「时刻 $T$ 真正站在节点 $N-1$ 上」的方案数。用矩阵快速幂计算，共约 $\lceil\log_2 T\rceil\le 30$ 轮，每轮一次 $S\times S$ 矩阵乘法。

Python 里的实现细节。 $S=90$ 时一次矩阵乘法是 $90^3=729000$ 次内层乘加， 纯三层 for 循环在 30 轮下会明显偏慢。这里改用按列打包：

• 把 $M$ 的每一行按固定位宽 SLOT = 32 压成一个 Python 大整数，$M$ 变成一个 长度 $S$ 的大整数元组；
• 计算 $(AB)[i][j]$ 时，sum(x * y for x, y in zip(A[i], packed_b)) 一次就得到 整行的结果，第 $j$ 段正好是第 $j$ 列的元素和，再按 32 位切回来。

这样做合法的依据是一个界：每个元素都 $<2009$，求和项只有 $S\le90$ 个，所以每段的值 不超过 $90\times2008^2\approx3.6\times10^8<2^{32}$，绝不会向相邻段进位。

快速幂中向量按行向量右乘推进（vec = vec * M）：从 $x_0$ 出发，把 $M$ 不断平方， 遇到 $T$ 的二进制位为 1 时再乘上去，得到 $x_0M^T$。注意方向不能反：$x_0M^T$ 的 第 $(N-1)\cdot9$ 个分量才是把起点成分送到终点的那一项。

下表用一个玩具图说明拆分后各状态的时间演化，图是 $0\xrightarrow{3}1$ 加上 $1$ 上权为 1 的自环，$T=4$。行是时刻 $t$，列是扩展图状态，单元格是「$t$ 时刻到达该状态」的走法数。

可以看到终点状态 $(1,0)$ 在 $t=3$ 才第一次变成 1，在 $t<3$ 时恒为 0。等待链把长边 占用的时间精确记账，所以「恰好 $T$」既不会把短于 $T$ 的走法算进来，也不会漏掉刚好 $T$ 的走法。（真实的 $T$ 极大，这张表只用于说明状态语义，实际计算走矩阵快速幂。）

推导与代码的对应。 代码里 build_matrix 就是上面的拆点：trans[u*CHAIN][v*CHAIN+c-1] = 1 是原边 $(u,0)\to(v,c-1)$，trans[v*CHAIN+k][v*CHAIN+k-1] = 1 是等待链；CHAIN = 9 是一个节点拆出的状态数。vec 就是行向量 $x_0$（只在 $(0,0)$ 处为 1），vec[(n-1)*CHAIN] 就是答案所在的 $(N-1,0)$ 分量；mat_mul 是唯一的乘法入口，pack_rows / unpack_row 负责 SLOT = 32 的按列打包； pow_vec 就是行向量右乘的快速幂（start · M^exp）。

代码

Python 版：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-09-30 23:56
# update_at: 2026-10-01 00:08

import sys
from array import array

MOD = 2009   # 题目要求的模数，每步都取模可让矩阵元素恒小于 2009
CHAIN = 9    # 每个原节点拆成 9 个状态，第 k 个表示「还需 k 步才真正到达」
SLOT = 32    # 行打包的位宽；一行的内积 <= 90*2008^2 < 2^32，所以段与段不会串位

Row = list[int]
Matrix = list[Row]


def pack_rows(mat: Matrix) -> tuple[int, ...]:
    """把每行的所有元素按固定位宽压进一个大整数，充当「一行乘整个矩阵」的常数。"""
    return tuple(sum(v << (SLOT * j) for j, v in enumerate(row)) for row in mat)


def unpack_row(bits: int, size: int) -> Row:
    """把打包好的乘积按 SLOT 位一段拆回一行，再对 2009 取模。"""
    return [v % MOD for v in array('I', bits.to_bytes(4 * size, 'little'))]


def mat_mul(a: Matrix, b: Matrix, size: int) -> Matrix:
    """矩阵乘法：a 的每一行各自与打包好的 b 相乘，即得结果矩阵的每一行。"""
    packed_b = pack_rows(b)
    return [unpack_row(sum(x * y for x, y in zip(row, packed_b)), size) for row in a]


def build_matrix(n: int, grid: list[str]) -> tuple[Matrix, int]:
    """把「边权 1~9 的 N 点图走恰好 T 步」改写成 9N 个点的无权 0/1 转移矩阵。

    状态 (v,k) 的含义：人已经踏上通往 v 的那条边、并且还要 k 个单位时间才真正落到 v。
    于是 (v,0) 才是「人站在 v 上」，而 (v,1)..(v,8) 只是把长边拆开后的等待态。
    """
    size = n * CHAIN
    # (u,0) 走一条耗时 w 的边后进入等待态 (v,w-1)，再靠链式状态逐个消耗剩余时间
    trans: Matrix = [[0] * size for _ in range(size)]
    for u in range(n):
        for v, ch in enumerate(grid[u]):
            if ch != '0':
                trans[u * CHAIN][v * CHAIN + int(ch) - 1] = 1
    # 链 (v,k) -> (v,k-1)：原地消耗一个单位时间，不改变最终要到达的节点
    for v in range(n):
        for k in range(1, CHAIN):
            trans[v * CHAIN + k][v * CHAIN + k - 1] = 1
    return trans, size


def pow_vec(mat: Matrix, exp: int, start: Row, size: int) -> Row:
    """求 start · mat^exp（行向量右乘），按 exp 的二进制位倍增：O(size^3 log exp)。

    方向不能反：x_k = x_{k-1}·M，因此只有右乘 M^{2^i} 才能累乘出 x_0·M^exp。
    """
    while exp:
        if exp & 1:                    # 行向量当 1×size 矩阵，复用同一个乘法入口
            start = mat_mul([start], mat, size)[0]
        exp >>= 1
        if exp:                        # 已是最后一个二进制位时不必再平方
            mat = mat_mul(mat, mat, size)
    return start


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    n, t = next(data), next(data)
    grid = [str(next(data)).zfill(n) for _ in range(n)]

    trans, size = build_matrix(n, grid)
    vec: Row = [1] + [0] * (size - 1)  # 时刻 0 唯一可达的状态是站在起点上的 (0,0)
    answer = pow_vec(trans, t, vec, size)
    print(answer[(n - 1) * CHAIN])     # 终点的落地状态 (N-1,0)


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-06 00:23
 * update_at: 2026-10-06 00:23
 */
#include <cstdio>

typedef long long ll;

const int MOD = 2009;   // 题目要求的模数
const int MAXN = 12;    // 原图节点数上限 N <= 10
const int CHAIN = 9;    // 每个原节点拆成 9 个状态：真正到达 + 8 个等待态
const int MAXS = MAXN * CHAIN; // 扩展图节点数上限 9N <= 90

int n;                  // 原图节点数
long long T;            // 要求的恰好时刻

char grid[MAXN][MAXN];  // grid[u][v] 为 '0' 无这条边，为 '1'..'9' 表示边权
int size_all;           // 扩展图节点数 size_all = n * CHAIN

ll base_mat[MAXS][MAXS]; // 扩展图的 0/1 邻接矩阵，也是快速幂的底数
ll res_mat[MAXS][MAXS];  // 累乘结果，最终为 M^T
ll tmp_mat[MAXS][MAXS];  // 矩阵乘法临时存放

// c = a * b (mod MOD)；运算结果恒小于 2009，用 ll 防止内层求和溢出。
void mat_mul(ll a[][MAXS], ll b[][MAXS], ll c[][MAXS]) {
    for (int i = 0; i < size_all; i++) {
        for (int j = 0; j < size_all; j++) {
            ll sum = 0;
            for (int k = 0; k < size_all; k++) {
                sum += a[i][k] * b[k][j];
            }
            c[i][j] = sum % MOD;
        }
    }
}

// 把 from 拷回 to，用于矩阵乘法后替换原矩阵。
void mat_copy(ll to[][MAXS], ll from[][MAXS]) {
    for (int i = 0; i < size_all; i++) {
        for (int j = 0; j < size_all; j++) {
            to[i][j] = from[i][j];
        }
    }
}

// 拆点建图：把「边权 1~9 的 N 点图走恰好 T 时间」变成「9N 个点的无权图走恰好 T 步」。
// 状态 (v,0) 表示真正站在节点 v 上，(v,k)(k>=1) 表示还差 k 步才落到节点 v。
void build_matrix() {
    // 原边：走一条耗时 w 的边，先花 1 步进入等待态 (v,w-1)，再沿等待链消耗剩余时间。
    for (int u = 0; u < n; u++) {
        for (int v = 0; v < n; v++) {
            if (grid[u][v] != '0') {
                base_mat[u * CHAIN][v * CHAIN + (grid[u][v] - '1')] = 1;
            }
        }
    }
    // 等待链 (v,k) -> (v,k-1)：原地消耗一个单位时间，终点不变。
    for (int v = 0; v < n; v++) {
        for (int k = 1; k < CHAIN; k++) {
            base_mat[v * CHAIN + k][v * CHAIN + k - 1] = 1;
        }
    }
}

int main() {
    scanf("%d %lld", &n, &T);
    for (int i = 0; i < n; i++) {
        scanf("%s", grid[i]);
    }

    size_all = n * CHAIN;
    build_matrix();

    // 单位矩阵作为累乘初值，做 M^T 的矩阵快速幂。
    for (int i = 0; i < size_all; i++) {
        res_mat[i][i] = 1;
    }
    while (T > 0) {
        if (T & 1LL) {
            mat_mul(res_mat, base_mat, tmp_mat);
            mat_copy(res_mat, tmp_mat);
        }
        mat_mul(base_mat, base_mat, tmp_mat);
        mat_copy(base_mat, tmp_mat);
        T >>= 1LL;
    }

    // 时刻 0 只有起点落地状态 (0,0) 为 1，故答案就是 M^T 第 0 行中 (N-1,0) 的分量。
    printf("%lld\n", res_mat[0][(n - 1) * CHAIN]);
    return 0;
}

复杂度

• 设扩展图规模 $S=9N\le90$。矩阵快速幂共 $\lceil\log_2 T\rceil\le30$ 轮，每轮一次 $S\times S$ 矩阵乘法（$O(S^3)$）和一次矩阵乘行向量（$O(S^2)$）。
• 时间复杂度 $O(S^3\log T)=O\bigl((9N)^3\log T\bigr)$，与 $T$ 成对数关系。 朴素逐时刻递推是 $O(T\cdot9N^2)$，两者在 $T=10^9$ 时相差约 $4\times10^4$ 倍。
• 空间复杂度 $O(S^2)=O\bigl((9N)^2\bigr)$，只存一个矩阵和打包后的 $S$ 个大整数， 与 $T$ 无关。

总结

「边权只有 1 到 9」这种小常数边权，是邻接矩阵快速幂的标志：把每条长边拆成 「1 步真正出发 + $w-1$ 步原地等待」，用 $9N$ 个状态把带权图变成无权图， 问题就退化成「恰好走 $T$ 步的走法数」。拆点的合法性来自等待链没有分支， 所以长边与等待链一一对应，既不会漏算也不会多算。

这类「小权值 + 长步数」的模型适用范围很广：只要边权是 $1$ 到 $W$ 的小整数， 就能用 $WN$ 个状态做拆点，代价是矩阵规模乘以 $W$。当 $W$ 变大到几十时， 还可以改用「边权二进制拆分」或直接在转移矩阵里放多个时间层的做法控制规模。

图示解析

1
2
3
4
5
6
7
8
9
10原图 G（N 点，边权 1..9，恰好 T 时间）
        |  拆点：每个点 v -> (v,0)..(v,8)，长边摊平成等待链
        v
扩展图 G'（S = 9N <= 90 点，全部边权 1）
        |  恰好 T 步的走法数 = 邻接矩阵 M 的 T 次幂分量
        v
行向量 x0 右乘 M^T   <==二进制拆分==>   30 轮  O(S^3 log T)
        |  列打包：一行内积 = 一次大整数乘法（32 位一段，不串位）
        v
答案 = (M^T)[(N-1)*9][0]  mod 2009

整条路线只有两个跳跃：先把「带权、恰好 $T$ 时间」翻译成「无权、恰好 $T$ 步」， 再把「$T$ 步」用二进制拆分压成 $\log T$ 轮矩阵乘法。前者靠拆点，后者靠快速幂。