P4159 [SCOI2009] 迷路
搬运工
题目链接
首先我们先考虑这道题的弱化版如何处理。假如所有的边权都是零和一。
这时他们的边权可以看做这两个点走一步到达之间的方案数。
而对于走 t 步，我们可以推出下列式子, \(f_{i,j}\) 表示从节点 \(i\) 到节点 \(j\) 的方案数。
是不是很熟悉,我们发现它就是矩阵乘法的式子。
对于这个，这里有一道题P2233 [HNOI2002] 公交车路线,我们直接考虑矩阵加速，即可求出。
回到这道题
通过观察，我们发现他的每一个边权都很小，不会超过九（其实这就暗示了解法）
我们不妨考虑把每一个点拆成9个边权为1或0的点，可以这样想象（当然也有另外的拆法，大同小异）
我们可以将第一个点拆成 \(1.0\ ,\ 1.1,\ 1.2,\ 1.3,\dots \ 1.8,\ 1.8\)
其中 \(1.0\) 代表的就是这个点，我们可以叫他“真点”
而对于 \(1.i\) 这样的点，它代表距离“真点” \(1\) 距离为 \(i\) 的点，我们叫它“假点”。
\(2\leq n\leq 10\) ,所以我们可以拆成 \(9n\cdot 9n\) 的矩阵。
在读入边权之前，我们需要将每个点的后八个假点每两个相邻的连接，边权为1 。
对于边权 \(u,v,w\)，我们将 \(u\) 连到 \(v.w\) 边权为1
这样就构造出了矩阵。然后直接跑矩阵快速幂就行。
对于求第 \(t\) 步的方案数，时间复杂度为 \(O(\ \ (9n)^3\log t\ \ )\)
代码如下
/*
* @Author: Ishar-zdl
* @Date: 2023-10-14 15:03:04
* @Last Modified by: Ishar-zdl
* @Last Modified time: 2023-10-15 07:51:30
*/
#include<bits/stdc++.h>
using namespace std;
inline int read(){
int x=0,f=1;char ch=getchar();
for(;ch<'0'||ch>'9';ch=getchar())if(ch=='-')f=-1;
for(;ch>='0'&&ch<='9';ch=getchar())x=(x<<1)+(x<<3)+(ch^48);
return x*f;
}
inline void write(int x){
if(x<0)putchar('-'),x=-x;
if(x>9)write(x/10);
putchar(x%10+48);
}
const int mod=2009,N=95;
struct mt{
int n,t[N][N];
inline mt(){memset(t,0,sizeof(t));}
inline void clear(){
memset(t,0,sizeof(t));
for(int i=1;i<=n;++i)t[i][i]=1;
}
inline mt operator*(const mt&b)const{
mt res;int r;res.n=b.n;
for(int i=1;i<=n;++i)
for(int j=1;j<=n;++j){
for(int k=1;k<=n;++k)
res.t[i][j]+=t[i][k]*b.t[k][j];
res.t[i][j]%=mod;
}
return res;
}
inline mt operator^(int p)const{
mt res,x=*this;res.n=x.n;
res.clear();
for(;p;p>>=1,x=x*x)
if(p&1)res=res*x;
return res;
}
}base;
int main(){
// freopen("in.in","r",stdin);
// freopen("out.out","w",stdout);
int n=read(),q=read();base.n=9*n;
int a;
for(int i=1;i<=n;++i){
for(int zc=i*9-7;zc<=i*9;zc++)
base.t[zc][zc-1]=1;
for(int j=1;j<=n;++j){
scanf("%1d",&a);
if(a)
base.t[i*9-8][j*9-9+a]=1;
}
}
base=base^q;
write(base.t[1][n*9-8]);
return 0;
}