[洛谷 4159][SCOI2009]迷路

题目链接

https://www.luogu.org/problem/P4159

题解

我们将一个点 \(i\) 拆分成 \(9\) 个点，设这九个点的编号为 \(9*i+1 \ldots 9*i+9\)。我们先从左到右给这九个点顺次连边。

如果原图中 \(i\) 和 \(j\) 之间有一条权值为 \(k\) 的边，我们就在新图中从 \(9*i+k\) 向 \(9*j+1\) 连一条边。

这么连边的意义是很明显的：我们发现从 \(i\) 号点到 \(j\) 号点刚好走了 \(k\) 条边。

剩下就是求邻接矩阵的幂了。可以参考 [TJOI2017]可乐 一题。

#include <iostream>
#include <cstring>
#define MOD 2009
using namespace std;
struct mat
{
 int a[105][105];
 mat()
 {
  memset(a,0,sizeof(a));
 }
}f;
long long n,t;
char s[15];
mat operator*(mat a,mat b)
{
 mat ans;
 for(int k=1;k<=n*9+1;k++)
  for(int i=1;i<=n*9+1;i++)
   for(int j=1;j<=n*9+1;j++)
    ans.a[i][j]=(ans.a[i][j]+a.a[i][k]*b.a[k][j])%MOD;
 return ans;
}
mat fpow(mat x,long long y)
{
 mat ans;
 for(int i=1;i<=n*9+1;i++)
  ans.a[i][i]=1;
 while(y)
 {
  if(y&1)ans=ans*x;
  x=x*x;
  y>>=1;
 }
 return ans;
}
int main()
{
 cin>>n>>t;
 for(int i=0;i<n;i++)
 {
  cin>>s;
  for(int j=i*9+1;j<=i*9+8;j++)
   f.a[j][j+1]=1;
  for(int j=0;j<n;j++)
   if(s[j]-='0')
    f.a[i*9+s[j]][j*9+1]=1;
 }
 cout<<fpow(f,t).a[1][(n-1)*9+1]<<endl;
 return 0;
}