P4159 [SCOI2009]迷路

传送门

先考虑只有 01 边权的情况

显然可以DP+矩阵加速

但是现在边权不止 1

然鹅最大也只有 9

所以从这里入手，把点拆成 9 个，然后点之间的边权也就可以变成 1 了

同样的转移和矩阵加速

注意点之间的连接关系

#include<iostream>

#include<algorithm>

#include<cstdio>

#include<cmath>

#include<cstring>

using namespace std;

inline int read()

{

    int x=,f=; char ch=getchar();

    while(ch<''||ch>'') { if(ch=='-') f=-; ch=getchar(); }

    while(ch>=''&&ch<='') { x=(x<<)+(x<<)+(ch^); ch=getchar(); }

    return x*f;

}

const int N=,mo=;

inline int fk(int x) { return x>=mo ? x-mo : x; }

int n,T,m;

struct matrix//矩阵乘法不解释

{

    int a[N][N];

    matrix () { memset(a,,sizeof(a)); }

    inline matrix operator * (const matrix &tmp) const {

        matrix res;

        for(int i=;i<=m;i++)

            for(int j=;j<=m;j++)

                for(int k=;k<=m;k++)

                    res.a[i][j]=fk(res.a[i][j]+a[i][k]*tmp.a[k][j]%mo);

        return res;

    }

}F,M;

matrix ksm(matrix X,int Y)//矩阵快速幂不解释

{

    matrix res;

    for(int i=;i<=m;i++) res.a[i][i]=;

    while(Y)

    {

        if(Y&) res=res*X;

        X=X*X; Y>>=;

    }

    return res;

}

char s[N];

int main()

{

    n=read(); T=read(); m=n*;

    for(int i=;i<=n;i++)//构造转移矩阵

    {

        int t=(i-)*+;

        for(int j=;j<;j++) M.a[t+j][t+j-]=;

        scanf("%s",s+);

        for(int j=;j<=n;j++)

        {

            if(s[j]=='') continue;

            M.a[t][(j-)*+s[j]-'']=;

        }

    }

    F.a[][]=;

    F=F*ksm(M,T);

    printf("%d",F.a[][(n-)*+]);

    return ;

}