题目描述

  有向图有 \(n(2\leq n\leq 10)\) 个节点，从节点 \(0\) 出发，必须恰好在 \(t(1\leq t\leq 10^9)\) 时刻到达节点 \(n-1\)。 现在给出该有向图（边权 \(1\) ~ \(9\)），求总共有多少种不同的路径。

分析

  首先有一个离散数学中的结论：用邻接矩阵 \(A\) 存无向图顶点间的关系，则 \(A^n\) 中的 \(a_{ij}\) 代表点 \(i\) 恰好走 \(n\) 步能到达点 \(j\) 的方案数。

  由于边权范围为 \(1\) ~ \(9\)，不能直接矩阵求幂，所以考虑如何建图：

  \(1.\) 把原图中的点拆成 \(9\) 个点：如果原图中的点为 \(x\)，则拆后的点为 \((x-1)\times 1+i(1\leq i\leq 9)\)，点 \(x\) 的 关键点 为 \((x-1)\times 9+1\)，并把点 \((x-1)\times 9+i(1\leq i\leq 8)\) 向点 \((x-1)\times 9+i+1(1\leq i\leq 8)\) 连边。

  \(2.\) 原图中的点之间连边：假设原图中点 \(x\) 与点 \(y\) 的边权为 \(w\)，则连接新图中的点 \((x-1)\times 9+w\) 和点 \((y-1)\times 9+1\)。

  假设原图的邻接矩阵为：\(\begin{bmatrix}2&1\\2&0\end{bmatrix}\)

  则新图为：

  这样从点 \(x\) 必须走 \(k\) 条边才能走到点 \(y\)，这时矩阵求幂即可。起点为 \(1\)，终点为 \((n-1)\times 9+1\)。

代码

#include<bits/stdc++.h>
using namespace std;
int n,t;
const int mod=2009;
struct matrix
{
    int mat[310][310];
    matrix()
    {
        memset(mat, 0, sizeof(mat));
    }
}A;
matrix mul(matrix A,matrix B)
{
    matrix ans;
    for(int i=1;i<=9*n;i++)
        for(int j=1;j<=9*n;j++)
            for(int k=1;k<=9*n;k++)
                ans.mat[i][j]=(ans.mat[i][j]+A.mat[i][k]*B.mat[k][j])%mod;
    return ans;
}
matrix matrix_pow(matrix a,int b)
{
    matrix ans;
    for(int i=1;i<=9*n;i++)
        for(int j=1;j<=9*n;j++)
            ans.mat[i][j]=(i==j);
    while(b)
    {
        if(b&1)
            ans=mul(ans,a);
        a=mul(a,a);
        b>>=1;
    }
    return ans;
}
int a[310][310];
int main()
{
    cin>>n>>t;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=8;j++)
            A.mat[(i-1)*9+j][(i-1)*9+j+1]=1;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            scanf("%1d",&a[i][j]);
            if(a[i][j]>0)
                A.mat[(i-1)*9+a[i][j]][(j-1)*9+1]=1;
        }
    }
    cout<<matrix_pow(A,t).mat[1][(n-1)*9+1]<<endl;
    return 0;
}