洛谷4159 [SCOI2009]迷路

题意

给出一个 $N$ 点有向图，从 $1$ 到 $N$ ，要求恰好 $T$ 时刻到达。

其中 $N\le 10$ ，边权 $\in[1,9]$ 。边权为 $0$ 代表没有边。

题解

考虑边权只可能为 $1$ 的情况。用 $f[i][j]$ 代表 $i\rightarrow j$ 恰好 $T$ 时刻到达的方案数，那么

$$f_T[i][j]=\sum_{k=1}^{N} f_{T-1}[i][k]\times f_1[k][j]$$

显然是矩阵快速幂的模型，$f_1$ 就是图的邻接矩阵，答案即为 ${f_1}^T[1][N]$ 。

这道题的边权为 $[1,9]$ ，虽然不能直接用上面的结论，但范围并不大，考虑将原图边权全部化为 $1$。

把每一个点拆分成 $9$ 个点，编号为 $[0,8]$ 。下面用 $(x,y)$ 表示第 $x$ 个点拆分后的编号为 $y$ 的点。连边如下：

1. $(x,y)\rightarrow (x,y-1) \ , \ y\in [1,8]$
2. 对于原来边权为 $w$ 的边 $s\rightarrow t$ ，连接 $(s,0)\rightarrow (t,w-1)$

可以发现这样就把所有的边权转化到 $x$ 点内部的过程。

连完边以后对这个 $9n\times 9n$ 的图求 ${f_1}^T[1][N]$ 即可得到答案。

#include<bits/stdc++.h>
#define ha 2009

using namespace std;

inline int read()
{
    char ch=getchar();
    int f=1,x=0;
    while (ch<'0' || ch>'9')
    {
        if (ch=='-') f=-1;
        ch=getchar();
    }
    while (ch>='0' && ch<='9')
    {
        x=x*10+ch-'0';
        ch=getchar();
    }
    return f*x;
}

int n,t;
char ch[15];
struct matrix {
    int n,s[95][95];
    matrix(int len=0) { n=len; memset(s,0,sizeof(s)); }
    matrix operator * (const matrix &x) const {
        matrix y;
        y.n=n;
        for (int i=1;i<=n;i++)
            for (int j=1;j<=n;j++)
                for (int k=1;k<=n;k++)
                    y.s[i][j]=(y.s[i][j]+s[i][k]*x.s[k][j]%ha)%ha;
        return y;
    }
};

inline int id(int &x,int y);
inline void init(matrix &x);
inline matrix qpow(matrix x,int y);

signed main()
{
    n=read(); t=read();
    matrix x(n*9);
    for (int i=1;i<=n;i++)
    {
        scanf("%s",ch+1);
        for (int j=1;j<=n;j++)
        {
            int a=ch[j]-'0';
            if (!a) continue;
            x.s[id(i,0)][id(j,a-1)]=1;
        }
        for (int j=1;j<=8;j++) x.s[id(i,j)][id(i,j-1)]=1;
    }
    x=qpow(x,t);
    return !printf("%d",x.s[1][n]);
}

inline int id(int &x,int y) { return x+y*n; }

inline void init(matrix &x) { for (int i=1;i<=x.n;i++) x.s[i][i]=1; }

inline matrix qpow(matrix x,int y)
{
    matrix ans(x.n); init(ans);
    while (y)
    {
        if (y&1) ans=ans*x;
        y>>=1;
        x=x*x;
    }
    return ans;
}