dinnerhunt

windy在有向图中迷路了。 该有向图有 N 个节点，windy从节点 0 出发，他必须恰好在 T 时刻到达节点 N-1。 现在给出该有向图，你能告诉windy总共有多少种不同的路径吗？ 注意：windy不能在某个节点逗留，且通过某有向边的时间严格为给定的时间。

题目链接🔗

[SCOI2009]迷路

题解

先忽略权值，默认权值为 $1$ ,这样我们可以列出 DP方程
$f_t[i][j]$ 表示 $i$ 到 $j$ 的长度为 $t$ 的路径有多少条
那么它的转移方程为

$f_t[i][j] = \sum^{n}_{k=1}f_{t-1}[i][k]*f_1[k][j]$

这个式子就是矩阵乘法的式子，然后因为矩阵乘法满足结合率

$f_t = f{t-1} \cdot f_1$

$f_t = f^t_1$

然后因为权值小，我们可以将每个点 $x$ 拆成 $(x,1-9)$ , $9$ 个点，
然后每个点 $(x,i)$ , 仅和 $(x,i-1)$ 相连
然后如果 $x,y$ 之间有条权值为 $k$ 的路径，那么 $(x,k)$ 与 $(y,1)$ 相连
然后直接求 $f_t[1][(n-1)*9+1]$ 即可

代码

#include <cstdio>
#include <algorithm>
#define ll long long
using namespace std;
struct matrix
{
    int n,m;
    ll a[200][200];
};
matrix matrix_mul(matrix A,matrix B,ll mod)
{
    matrix C;
    C.n = A.n;
    C.m = B.m;
    for(int i=1;i<=A.n;i++)
        for(int j=1;j<=B.m;j++)
        {
            C.a[i][j] = 0;
            for(int k = 1;k<=A.m;++k)
                (C.a[i][j] += (A.a[i][k] * B.a[k][j])%mod)%=mod;
        }
    return C;
}
matrix unit(int n)
{
    matrix res;
    res.n = res.m = n;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            res.a[i][j] = (i==j);
    return res;
}
matrix matrix_pow(matrix A,ll n,ll mod)
{
    matrix res = unit(A.n), temp = A;
    for(;n;n>>=1)
    {
        if(n&1) res = matrix_mul(res,temp,mod);
        temp = matrix_mul(temp,temp,mod);
    }
    return res;
}
char str[20];
int main()
{
    // freopen("a.in","r",stdin);
    // freopen("k.out","w",stdout);
    ll n,t;
    scanf("%lld %lld",&n,&t);
    matrix A;A.n = A.m = 9*n;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=8;j++)
            A.a[(i-1)*9+j][(i-1)*9+j+1] = 1;
    for(int i=1;i<=n;i++)
    {
        scanf("%s",str+1);
        for(int j=1;j<=n;j++)
        {
            int k = str[j] - '0';
            if(!k) continue;
            A.a[(i-1)*9+k][(j-1)*9+1] = 1;
        }
    }
    A = matrix_pow(A,t,2009);
    printf("%lld",A.a[1][n*9-8]);
    return 0;
}