bzoj 1297: [SCOI2009]迷路

.

题意：给定一个有向图，问有多少条从1到n的路径长度为t。
题解：矩阵乘法+快速幂
t的范围是1e9，一看就是矩阵乘法，然后就不会了。。。膜了题解后可以发现，当每条边的长度都为1时，把邻接矩阵乘t次，[0][n-1]就是答案，因为我们可以把矩阵看成i到j的路径数。所以我们就可以把一个点拆成9个点，每个点拆的第j个点向第j-1个点连边。i到j长度为k就是把i的第1个点和j的第k个点连边。边权都是1。
代码：

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

struct matrix
{
    int x,y,a[100][100];
    matrix()
    {
        memset(a,0,sizeof(a));
    }
    int* operator[](int x)
    {
        return a[x];
    }
}a;
int n,t;
const int mod=2009;

inline int get(int x,int y)
{
    return x*9+y;
}
matrix operator*(matrix x,matrix y)
{
    matrix ans;
    ans.x=x.x;
    ans.y=y.y;
    for(int i=0;i<ans.x;i++)
    for(int j=0;j<ans.y;j++)
    for(int k=0;k<x.y;k++)
    ans[i][j]=(ans[i][j]+x[i][k]*y[k][j])%mod;
    return ans;
}
matrix pow(matrix x,int y)
{
    matrix ans;
    if(y==0)
    {
        for(int i=1;i<=x.x;i++)
        ans[i][i]=1;
        ans.x=ans.y=x.x;
        return ans;
    }
    if(y==1)
    return x;
    ans=pow(x,y>>1);
    ans=ans*ans;
    if(y&1)
    ans=ans*x;
    return ans;
}
int main()
{
    scanf("%d%d",&n,&t);
    a.x=a.y=n*9;
    for(int i=0;i<n;i++)
    {
        for(int j=1;j<9;j++)
        a[get(i,j)][get(i,j-1)]=1;
    }
    for(int i=0;i<n;i++)
    {
        char s[11];
        scanf("%s",s);
        for(int j=0;j<n;j++)
        {
            if(s[j]>'0')
            a[get(i,0)][get(j,s[j]-'0'-1)]=1;
        }
    }/*
    for(int i=0;i<a.x;i++)
    {
        for(int j=0;j<a.y;j++)
        printf("%d ",a[i][j]);
        puts("");
    }*/
    matrix ans=pow(a,t);
    printf("%d",ans[get(0,0)][get(n-1,0)]);
}