python/TangDou/AcWing/Floyd/P4159.cpp

#include <bits/stdc++.h>
using namespace std;

typedef long long LL;
const int MOD = 2009;
const int N = 110;

int g[N][N], a[N][N];
int n, t;

//矩阵乘法
void mul(int c[][N], int a[][N], int b[][N]) {
    int t[N][N] = {0};
    int M = n * 9;
    for (int i = 1; i <= M; i++) {
        for (int j = 1; j <= M; j++)
            for (int k = 1; k <= M; k++)
                t[i][j] = (t[i][j] + (LL)(a[i][k] * b[k][j]) % MOD) % MOD;
    }
    memcpy(c, t, sizeof t);
}

int main() {
    // n个节点，t时刻
    scanf("%d %d", &n, &t);

    for (int i = 1; i <= n; i++) { //原图有n个节点

        /* 1点拆9点
          1-> 1~9
          2-> 10~18
          3-> 19~17
          ...

          拆开的点之间的权值是1
         */
        for (int j = 1; j < 9; j++) // 1点拆9点，注意收尾处是小于号
            g[(i - 1) * 9 + j][(i - 1) * 9 + j + 1] = 1;

        //从下标1开始读入原图中i号节点与其它各节点间的边权
        char s[11];
        scanf("%s", s + 1);

        //遍历一下输入的各点间关系图
        for (int j = 1; j <= n; j++)
            //如果i->j 存在边，并且边权 = s[j]
            //比如 1->8, 边权为3; 则 从3'->64'创建一条边权为1的边
            if (s[j] > '0') g[(i - 1) * 9 + s[j] - '0'][(j - 1) * 9 + 1] = 1;
    }

    //复制原始底图
    memcpy(a, g, sizeof g);

    //因为是复制出来，t次幂就变成了t-1次幂
    t--;

    //矩阵快速幂
    while (t) {
        if (t & 1) mul(g, g, a);
        mul(a, a, a);
        t >>= 1;
    }

    //输出结果
    printf("%d\n", g[1][(n - 1) * 9 + 1]);
    return 0;
}