[文章目录]
Description
HH有个一成不变的习惯，喜欢饭后百步走。所谓百步走，就是散步，就是在一定的时间 内，走过一定的距离。 但是同时HH又是个喜欢变化的人，所以他不会立刻沿着刚刚走来的路走回。 又因为HH是个喜欢变化的人，所以他每天走过的路径都不完全一样，他想知道他究竟有多 少种散步的方法。 现在给你学校的地图（假设每条路的长度都是一样的都是1），问长度为t，从给定地点A走到给定地点B共有多少条符合条件的路径，N ≤ 20，M ≤ 60，t ≤ 2^30，0 ≤ A,B
t那么大，显然矩乘。由于不能回头走，所以我们把边设为状态。dp[i][j]表示i时刻走了j这条边的方案数。矩乘加速第一维即可。时间复杂度O()
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
const int mod=45989;
int n,m,l,s,t;
int head[30],to[200],nxt[200],cnt=1;
inline void add(int x,int y)
{
to[++cnt]=y;
nxt[cnt]=head[x];
head[x]=cnt;
}
struct matrix1
{
int a[130][130];
matrix1(){memset(a,0,sizeof a);}
matrix1 operator * (const matrix1 &z)const
{
matrix1 re;
for(int i=2;i<=cnt;++i)
for(int j=2;j<=cnt;++j)
for(int k=2;k<=cnt;++k)
re.a[i][j]=(re.a[i][j]+a[i][k]*z.a[k][j])%mod;
return re;
}
};
struct matrix2
{
int a[130];
matrix2(){memset(a,0,sizeof a);}
matrix2 operator * (const matrix1 &z)const
{
matrix2 re;
for(int i=2;i<=cnt;++i)
for(int j=2;j<=cnt;++j)
re.a[i]=(re.a[i]+a[j]*z.a[j][i])%mod;
return re;
}
};
int main()
{
scanf("%d%d%d%d%d",&n,&m,&l,&s,&t);
int x,y;
for(int i=1;i<=m;++i)
{
scanf("%d%d",&x,&y);
add(x,y); add(y,x);
}
matrix1 I;
for(int i=2;i<=cnt;++i)
for(int j=head[to[i]];j;j=nxt[j]) if(j!=(i^1))
I.a[i][j]=1;
matrix2 ans;
for(int i=head[s];i;i=nxt[i]) ans.a[i]=1;
l--;
while(l)
{
if(l&1) ans=ans*I;
I=I*I; l>>=1;
}
int fna=0;
for(int i=head[t];i;i=nxt[i])
fna=(fna+ans.a[i^1])%mod;
printf("%d",fna);
return 0;
}