洛谷P4159 [SCOI2009] 迷路 题解

题目链接：P4159 [SCOI2009] 迷路

题意：该有向图有 $n$ 个节点，节点从 $1$ 至 $n$ 编号，windy 从节点 $1$ 出发，他必须恰好在 $t$ 时刻到达节点 $n$。

现在给出该有向图，你能告诉 windy 总共有多少种不同的路径吗？

答案对 $2009$ 取模。

注意：windy 不能在某个节点逗留，且通过某有向边的时间严格为给定的时间。

题目给出了邻接矩阵

首先，根据矩阵乘法的性质，我们可以发现

不考虑题目的限制，当矩阵仅由01构成时

$M^2$ 的意义就是只通过两条边（此时边权均为 $1$ ）能到达每个结点的方案数

则此时答案就是 $M^t$

可是题目给出的矩阵，至多有 $10$

怎么办呢？考虑把它转化新的矩阵（仅有01构成的）

对于初始矩阵的每个节点，把它化为 $x_i$ 个结点

其中 $x_i$ 表示出边边权的最大值

如下图

“拆点”操作

可以发现这样的话仍然是满足题意的

为什么呢？因为可以更新答案的那条路径

一定走到了 $x_i$ 号节点，正准备走到原来的另一个节点

不是很好解释，自己多画几张图试试就知道了（我知道你们懒，给你们画一个）

“拆点”操作

那么这题就很简单了

时间复杂度 $O(n^3\log t)$

代码如下

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF ((int)0x3f3f3f3f3f3f3f3f)
#define inf ((int)0xc0c0c0c0c0c0c0c0)
#define N (int)(25)
const int p=2009;
int n,t;
struct mat
{
    int n,g[205][205];
    void clear()
    {
        memset(g,0,sizeof(g));
    }
    mat operator*(const mat &o)const
    {
        static mat tmp;
        tmp.n=n;tmp.clear();
        for(int i=1; i<=n; i++)
            for(int k=1; k<=n; k++)
            {
                int r=g[i][k]%p;
                for(int j=1; j<=n; j++)
                    tmp.g[i][j]=(tmp.g[i][j]+r*o.g[k][j]%p)%p;
            }
        return tmp;
    }
}M;

mat qpow(mat a,int b)
{
    static mat ans,base=a;
    ans.n=a.n;ans.clear();
    for(int i=1; i<=ans.n; i++)
        ans.g[i][i]=1;
    while(b)
    {
        if(b&1)ans=ans*base;
        base=base*base;
        b>>=1;
    }
    return ans;
}
int ck(int i,int j)
{
    return (i-1)*10+j;
}
signed main()
{
    scanf("%lld%lld",&n,&t);
    M.n=n*10;M.clear();
    for(int i=1; i<=n; i++)
    {
        for(int j=1; j<10; j++)
            M.g[ck(i,j)][ck(i,j+1)]=1;
        for(int j=1,x; j<=n; j++)
        {
            scanf("%1lld",&x);
            if(x)M.g[ck(i,x)][ck(j,1)]=1;
        } 
    }
    // for(int i=1; i<=M.n; i++)
    //     for(int j=1; j<=M.n; j++)
    //         printf("%lld%c",M.g[i][j]," \n"[j==M.n]);
    M=qpow(M,t);
    printf("%lld\n",M.g[1][ck(n,1)]);
    return 0;
}