思路与算法

边权为1至9，直接按时间DP需处理最多 $10^9$ 秒。把每个节点 $u$ 拆成9个状态 $(u,r)$，其中 $r=0,\ldots,8$ 表示还需多少秒到达 $u$，$r=0$ 才是真正处于原节点。

对 $r>0$，加入单位时间转移 $(u,r)\to(u,r-1)$。原有边 $u\to v$ 耗时 $w$，加入单位时间转移 $(u,0)\to(v,w-1)$。这样从原节点出发，第一秒进入剩余 $w-1$ 秒的状态，之后倒计时，到达 $(v,0)$ 总共恰好 $w$ 秒。这些中间状态表示正在边上行走，不是允许在原节点停留。矩阵字符0表示没有边，不能当作0耗时转移。

共有 $D=9N\le90$ 个状态。定义列向量计数，矩阵 $A_{\text{新},\text{旧}}$ 记录一步转移数。初始只有 $(0,0)$ 为1，$T$ 秒后分布为 $A^T V_0$。用二进制矩阵幂，取 $A^T$ 中从 $(0,0)$ 到 $(N-1,0)$ 的元素，模2009。不能把尚在通向终点的中间状态也加入答案。路径允许重复经过节点，每次都按边给定时间行走。

正确性说明

任一原图边耗时 $w$，在拆点图中恰对应长度 $w$ 的唯一单位转移链，且中间状态只有一个倒计时出口，不会提前离开或额外停留。将原路径各边依次替换为对应链，得到总单位步数等于原路径总耗时的拆点路径。反之，从实节点状态出发，任一拆点路径必须完整倒计时后才能继续选择原边，因此可唯一还原为原路径。终点取剩余时间0，保证已经真正到达。两类路径在耗时与方案上构成一一对应。

矩阵乘法的中间状态枚举将两段路径相接，所以矩阵幂的目标元素正好统计指定长度的全部拆点路径。快速幂与连续 $T$ 次转移等价，单位矩阵为零步转移基准。由上述对应，所得元素恰为原图中总耗时为 $T$ 的目标路径数。逐次取模保持计数同余，输出正确。

复杂度

令 $D=9N$。分配并初始化转移矩阵、单位矩阵耗时 $O(D^2)$，建边和倒计时链 $O(N^2+D)$；一次稠密矩阵乘法 $O(D^3)$，二进制幂 $O(\log(T+1))$ 轮。含初始化总时间 $O(D^2+N^2+D^3\log(T+1))$，额外空间 $O(D^2)$，与 $T$ 不呈线性增长。程序跳过零元素只改善常数，不改变上述上界。

易错点

1. 状态总数是 $9N$，剩余时间0至8；权值9的边进入剩余8状态，第一秒也要算在边耗时内。
2. 字符0为无边，不允许原节点无故停留；有自环时只能按自环实际耗时行走。
3. 固定列向量约定，写入矩阵时是新状态行、旧状态列；最终取终点实状态对应的行和起点实状态对应的列。
4. 求精确时间路径计数，不是最短路，也不是耗时不超过 $T$ 的总数。中途重复经过节点与合法自环均应保留。
5. 每次累加一个乘积就对2009取模，模内乘积加部分和小于 $2009^2$，32位有符号累加已安全。不能先累加90个未经取模的乘积。
6. 覆盖无路、权值9、最大 $T$、稠密图、多路径快速增长及原站两个样例。独立答案直接在原带权图上用生成函数、行列式及系数折半求值，未重复标程的拆点矩阵幂；数据非官方原版。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;
const int MOD = 2009;
using Matrix = vector<vector<int>>;
Matrix multiply(const Matrix &a, const Matrix &b) {
    int n = a.size();
    Matrix c(n, vector<int>(n));
    for (int i = 0; i < n; i++)
        for (int k = 0; k < n; k++)
            if (a[i][k]) {
                int value = a[i][k];
                for (int j = 0; j < n; j++)
                    c[i][j] = (c[i][j] + value * b[k][j]) % MOD;
            }
    return c;
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    long long time;
    cin >> n >> time;
    int size = 9 * n;
    Matrix base(size, vector<int>(size)), result(size, vector<int>(size));
    for (int i = 0; i < size; i++)
        result[i][i] = 1;
    for (int u = 0; u < n; u++) {
        for (int k = 1; k < 9; k++)
            base[u * 9 + k - 1][u * 9 + k] = 1;
        string row;
        cin >> row;
        for (int v = 0; v < n; v++) {
            int w = row[v] - '0';
            if (w)
                base[v * 9 + w - 1][u * 9]++;
        }
    }
    while (time) {
        if (time & 1)
            result = multiply(result, base);
        base = multiply(base, base);
        time >>= 1;
    }
    cout << result[(n - 1) * 9][0] << '\n';
}