[SCOI2009]迷路

题目

题目描述

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

输入输出格式

输入格式：

第一行包含两个整数，N T。接下来有 N 行，每行一个长度为 N 的字符串。第i行第j列为’0’表示从节点i到节点j没有边。为’1’到’9’表示从节点i到节点j需要耗费的时间。

输出格式：

包含一个整数，可能的路径数，这个数可能很大，只需输出这个数除以2009的余数。

输入输出样例

输入样例#1：

2 2
11
00

输出样例#1：

输入样例#2：

输出样例#2：

说明

【样例解释一】

0->0->1

【数据范围】

30%的数据，满足 2 <= N <= 5 ； 1 <= T <= 30 。

100%的数据，满足 2 <= N <= 10 ； 1 <= T <= 1000000000 。

题解

求两点之间路径条数的式子$d_{i,j}=\sum_{k=1}^{n}d_{i,k}\times d_{k,j}$可以用矩阵乘法转移，但是只适用于边长为$1$的情况

这个题边长不为$1$该怎么搞呢？

注意边长虽然不是$1$，但是都不超过$10$，所以可以把一个点拆成$9$个点，依次相连，分别代表每个长度的边，如果$i$与$j$有一条长度为$k$的边相连，相当于$i$的$k$号点与$j$有一条长度为$1$的边相连

然后就可以矩乘了，想搞从$0$开始的结果搞错编号了qaq……

代码

# include<iostream>
# include<cstring>
# include<cstdio>
# include<algorithm>
# define pu(x,y) x*9+y
using namespace std;
const int mod=2009,MAX=101;
int n,t;
struct p{
    int a[MAX][MAX];
    void cle_ar()
    {
        for(int i=0;i<n;++i)
          for(int j=0;j<n;++j)
            a[i][j]=0;
    }
    void beg_in()
    {
        cle_ar();
        for(int i=0;i<n;++i)
          a[i][i]=1;
    }
}a;
char A[MAX][MAX];
p operator *(p a,p b)
{
    p ans;
    ans.cle_ar();
    for(int i=0;i<n;++i)
      for(int j=0;j<n;++j)
        for(int k=0;k<n;++k)
          {
          	ans.a[i][j]+=a.a[i][k]*b.a[k][j]%mod;
          	if(ans.a[i][j]>=mod) ans.a[i][j]-=mod;
          }
    return ans;
}
p Pow(p a,int b)
{
    p ans;
    ans.beg_in();
    for(;b;b>>=1,a=a*a)
      if(b&1) ans=ans*a;
    return ans;
}
int main()
{
    scanf("%d%d",&n,&t);
    for(int i=0;i<n;++i)
      {
      	scanf("%s",A[i]);
      	for(int j=0;j<n;++j)
      	  if(A[i][j]!='0')
            a.a[pu(i,A[i][j]-'0'-1)][pu(j,0)]=1;
      	for(int j=1;j<=8;++j)
      	  a.a[pu(i,j-1)][pu(i,j)]=1;
      }
    n*=9;
    return printf("%d",Pow(a,t).a[0][n-9]),0;
}

题目