Description：

一个有向图，每条边的边权都为 $0$ ~ $9$ ，问从一到 $n$ 长度恰好为 $t$ 的路径条数。

$1\le n \le 10,1\le t\le 10^9$

Solution：

肯定是矩阵快速幂，有边权不好操作，可以把一条边拆点，拆成边权 $-1$ 个点，就可以直接矩阵快速幂，但是这样点有很多冗余，可以把每个点拆成 $9$ 个点 $p_{i,1},p_{i,2},\dots,p_{i,9}$ ，每个点向下一个点连边，然后连从 $i$ 到 $j$ 边权为 $k$ 的边就连一条 $p_{i,k}\to p_{j,1}$ 就行了。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cstring>

using namespace std;

int n,t;

#define MAXN 12

int p[MAXN][MAXN];

int getc()

{

    char c = getchar();

    while(!isdigit(c))c = getchar();

    return c - '0';

}

#define MOD 2009

#define MAXT 110

struct matrix

{

    int m[MAXT][MAXT];

    matrix(){memset(m,0,sizeof(m));}

    friend matrix operator * (matrix a,matrix b)

    {

        matrix c;

        for(int i = 1;i <= 9 * n;++i)

        {

            for(int j = 1;j <= 9 * n;++j)

            {

                for(int k = 1;k <= 9 * n;++k)

                {

                    c.m[i][j] = (c.m[i][j] + a.m[i][k] * b.m[k][j] % MOD) % MOD;

                }

            }

        }

        return c;

    }

}f;

int main()

{

    scanf("%d%d",&n,&t);

    for(int i = 1;i <= n;++i)

		for(int j = 1;j < 9;++j)

			f.m[(i - 1) * 9 + j][(i - 1) * 9 + j + 1] = 1;

    for(int i = 1;i <= n;++i)

    {

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

        {

            p[i][j] = getc();if(p[i][j] == 0)continue;

            f.m[(i - 1) * 9 + p[i][j]][(j - 1) * 9 + 1] = 1; 

        }

    }

    matrix res = f;--t;

    while(t > 0)

    {

        if(t & 1)res = res * f;

        f = f * f;

        t = t >> 1;

    }

    cout << res.m[1][(n - 1) * 9 + 1] << endl;

    return 0;

}