[BZOJ]1297: [SCOI2009]迷路

题目大意：给定一个有n个点的图的邻接矩阵，边权范围1~9，问从点0走到点n-1恰好走了长为T的路径的方案数。（n<=10，T<=10^9）

思路：由于边权较小，我们把每个点拆成9个点，分别为该点，离该点距离还差1，还差2……还差8，这样我们就可以把原图重构成一个边权均为1的图。用f[i][j]表示走了长为i的路径之后到点j（重构后的）的方案数，则f[i]=f[i-1]*新的邻接矩阵，矩阵乘法快速幂加速DP即可，复杂度O((9n)^3*logT)。

#include<cstdio>
#include<cstring>
#define MN 10
#define ML 90
#define MOD 2009
struct mat
{
    int z[ML][ML];
    mat operator*(mat b)
    {
        mat c;int i,j,k;
        memset(c.z,0,sizeof(c.z));
        for(i=0;i<ML;++i)for(k=0;k<ML;++k)if(z[i][k])
            for(j=0;j<ML;++j)c.z[i][j]=(c.z[i][j]+z[i][k]*b.z[k][j])%MOD;
        return c;
    }
}ans,t;
char g[MN+5][MN+5];
int main()
{
    int n,m,i,j;
    scanf("%d%d",&n,&m);
    for(i=0;i<n;++i)scanf("%s",g[i]);
    for(i=0;i<n;++i)
    {
        for(j=1;j<9;++j)t.z[i*9+j][i*9+j-1]=1;
        for(j=0;j<n;++j)if(g[i][j]>'0')t.z[i*9][j*9+g[i][j]-'1']=1;
    }
    for(ans.z[0][0]=1;m;m>>=1,t=t*t)if(m&1)ans=ans*t;
    printf("%d",ans.z[0][n*9-9]);
}