luogu4159 迷路 (矩阵加速)

考虑如果只有距离为1的边，那我用在时间i到达某个点的状态数矩阵 乘上转移矩阵（就是边的邻接矩阵），就能得到i+1时间的

然后又考虑到边权只有1~9，那可以把边拆成只有距离为1的

具体做法是一个点拆成9个然后串联

#include<bits/stdc++.h>
#define pa pair<ll,ll>
#define CLR(a,x) memset(a,x,sizeof(a))
#define MP make_pair
using namespace std;
typedef long long ll;
const int maxn=12,maxm=105,P=2009;

inline char gc(){
    return getchar();
    static const int maxs=1<<16;static char buf[maxs],*p1=buf,*p2=buf;
    return p1==p2&&(p2=(p1=buf)+fread(buf,1,maxs,stdin),p1==p2)?EOF:*p1++;
}
inline ll rd(){
    ll x=0;char c=gc();bool neg=0;
    while(c<'0'||c>'9'){if(c=='-') neg=1;c=gc();}
    while(c>='0'&&c<='9') x=(x<<1)+(x<<3)+c-'0',c=gc();
    return neg?(~x+1):x;
}

int id[maxn][maxn],N,M,T;
int trans[maxm][maxm],tmp[maxm][maxm],ans[maxm][maxm];

int main(){
    //freopen("","r",stdin);
    int i,j,k=0;
    N=rd();T=rd();
    for(i=1;i<=N;i++){
        for(j=1;j<=9;j++){
            id[i][j]=++M;
            if(j!=1) trans[id[i][j]][id[i][j-1]]=1;
        }
    }
    for(i=1;i<=N;i++){
        char s[13];scanf("%s",s+1);
        for(j=1;j<=N;j++){
            if(s[j]!='0') trans[id[i][1]][id[j][s[j]-'0']]=1;
        }
    }
    T--;
    memcpy(ans,trans,sizeof(ans));
    while(T){
        if(T&1){
            CLR(tmp,0);
            for(i=1;i<=M;i++){
                for(j=1;j<=M;j++){
                    for(k=1;k<=M;k++){
                        tmp[i][j]=(tmp[i][j]+ans[i][k]*trans[k][j])%P;
                    }
                }
            }
            memcpy(ans,tmp,sizeof(tmp));
        }
        CLR(tmp,0);
        for(i=1;i<=M;i++){
            for(j=1;j<=M;j++){
                for(k=1;k<=M;k++){
                    tmp[i][j]=(tmp[i][j]+trans[i][k]*trans[k][j])%P;
                }
            }
        }
        memcpy(trans,tmp,sizeof(tmp));
        T>>=1;
    }
    printf("%d
",ans[id[1][1]][id[N][1]]);
    return 0;
}