Description
HH有个一成不变的习惯，喜欢饭后百步走。所谓百步走，就是散步，就是在一定的时间 内，走过一定的距离。 但 是同时HH又是个喜欢变化的人，所以他不会立刻沿着刚刚走来的路走回。 又因为HH是个喜欢变化的人，所以他每 天走过的路径都不完全一样，他想知道他究竟有多 少种散步的方法。 现在给你学校的地图（假设每条路的长度都 是一样的都是1），问长度为t，从给定地 点A走到给定地点B共有多少条符合条件的路径
第一行：五个整数N，M，t，A，B。 N表示学校里的路口的个数 M表示学校里的 路的条数 t表示HH想要散步的距离 A表示散步的出发点 B则表示散步的终点。 接下来M行 每行一组Ai，Bi，表示从路口Ai到路口Bi有一条路。 数据保证Ai ！= Bi,但不保证任意两个路口之间至多只有一条路相连接。 路口编号从0到N -1。 同一行内所有数据均由一个空格隔开，行首行尾没有多余空格。没有多余空行。 答案模45989。 N ≤ 20，M ≤ 60，t ≤ 2^30，0 ≤ A,B
Output
一行，表示答案。
4 5 3 0 0
0 1
0 2
0 3
2 1
3 2
Sample Output
4
想法
数据范围提示我用矩阵乘法。 其中每个点表示一条路而不是一个点。 然后好像没什么可说的了。。。。
代码
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#define P 45989
using namespace std;
typedef long long ll;
const int SZ = 140;
int n,m;
struct matrix{
ll a[SZ][SZ];
matrix() { memset(a,0,sizeof(a)); }
void init() { for(int i=0;i<SZ;i++) a[i][i]=1; }
matrix operator * (const matrix &b) const{
matrix c;
for(int i=0;i<m;i++)
for(int j=0;j<m;j++)
for(int k=0;k<m;k++)
(c.a[i][j]+=a[i][k]*b.a[k][j])%=P;
return c;
}
matrix operator *= (const matrix &b) { return *this=*this*b; }
};
matrix Pow_mod(matrix x,ll y){
matrix ret; ret.init();
while(y){
if(y&1) ret*=x;
x*=x;
y>>=1;
}
return ret;
}
struct edge{
int fr,to;
}e[140];
int A,B;
ll t;
int main()
{
int u,v;
scanf("%d%d%lld%d%d",&n,&m,&t,&A,&B);
for(int i=0;i<m;i++){
scanf("%d%d",&u,&v);
e[i*2].fr=u; e[i*2].to=v;
e[i*2+1].fr=v; e[i*2+1].to=u;
}
m*=2;
matrix a,b;
for(int i=0;i<m;i++)
if(e[i].fr==A) b.a[0][i]=1;
for(int i=0;i<m;i++)
for(int j=0;j<m;j++)
if(e[i].to==e[j].fr){
if(i/2==j/2) continue;
a.a[i][j]=1;
}
a=Pow_mod(a,t-1);
b=b*a;
ll ans=0;
for(int i=0;i<m;i++)
if(e[i].to==B)
(ans+=b.a[0][i])%=P;
printf("%lld\n",ans);
return 0;
}
转载于:https://www.cnblogs.com/lindalee/p/8552510.html
相关资源：数据结构—成绩单生成器
