BZOJ 1297

应当是简单题。

发现边权的数量很小，所以我们暴力把一个点拆成$9$个点，然后把$(x, i)$到$(x, i + 1)$连边，代表转移一次之后可以走回来；对于每一条存在的边$(i, j, k)$，把$(i, k)$向$(j, 1)$连边，代表走一条路。然后用这个矩阵乘$T$次即可，这样子最后的答案$ans = [(1, 1)][(n, 1)]$格子的值。

记$m = 9 * n$，时间复杂度为$O(m^3logT)$。

Code：

#include 
      
       #include 
       
        using namespace std;const int N = 15;const int M = 105;const int P = 2009;int n, tim;inline void inc(int &x, int y) {    x += y;    if(x >= P) x -= P;}inline int id(int x, int k) {    return (x - 1) * 9 + k;}struct Matrix {    int len, wid, s[M][M];    inline void init(int r, int c) {        len = r, wid = c;        memset(s, 0, sizeof(s));    }     friend Matrix operator * (const Matrix &x, const Matrix &y) {        Matrix res; res.init(x.len, y.wid);        for(int k = 1; k <= x.wid; k++)            for(int i = 1; i <= x.len; i++)                for(int j = 1; j <= y.wid; j++)                    inc(res.s[i][j], x.s[i][k] * y.s[k][j] % P);        return res;    }    inline void print() {        for(int i = 1; i <= len; i++, printf("\n"))            for(int j = 1; j <= wid; j++)                printf("%d ", s[i][j]);    }} f;inline Matrix fpow(Matrix x, int y) {    Matrix res; res.init(x.len, x.wid);    for(int i = 1; i <= x.len; i++) res.s[i][i] = 1;    for(; y > 0; y >>= 1) {        if(y & 1) res = res * x;        x = x * x;    }    return res;}int main() {    scanf("%d%d", &n, &tim);    f.init(9 * n, 9 * n);    for(int i = 1; i <= n; i++) {        char str[N];        scanf("%s", str + 1);        for(int j = 1; j <= n; j++) {            int k = str[j] - '0';            if(!k) continue;            f.s[id(i, k)][id(j, 1)] = 1;        }        for(int j = 2; j <= 9; j++)            f.s[id(i, j - 1)][id(i, j)] = 1;    }//    f.print();    f = fpow(f, tim); //   f.print();    printf("%d\n", f.s[id(1, 1)][id(n, 1)]);    return 0;}