1875: [SDOI2009]HH去散步

Time Limit: 20 Sec Memory Limit: 64 MB
Submit: 2333 Solved: 1204
[Submit][Status][Discuss]

Description

HH有个一成不变的习惯，喜欢饭后百步走。所谓百步走，就是散步，就是在一定的时间内，走过一定的距离。但

是同时HH又是个喜欢变化的人，所以他不会立刻沿着刚刚走来的路走回。又因为HH是个喜欢变化的人，所以他每

天走过的路径都不完全一样，他想知道他究竟有多少种散步的方法。现在给你学校的地图（假设每条路的长度都

是一样的都是1），问长度为t，从给定地点A走到给定地点B共有多少条符合条件的路径

Input

第一行：五个整数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

一行，表示答案。

Sample Input

4 5 3 0 0
0 1
0 2
0 3
2 1
3 2

Sample Output

不能沿着刚刚走来的路走回
然后就很烦啊

解决方案：把双向边拆成两条单向边后按边建矩阵就不会走回去啦啦啦~(≧▽≦)/~

#include<iostream>
#include<cstdio>
#define M 45989
#define LL long long 
using namespace std;

int i,m,n,j,k,a,b,t, x,y,s[1000][2],ans;

struct vv
{
	int g[200][200];
} ch,f,cs,l;

vv cheng(vv a,vv b)
{
	vv d=ch;
	for(int i=1;i<=m+m;i++)
		for(int j=1;j<=m+m;j++) 
			for(int k=1;k<=m+m;k++) 
				d.g[i][j]=(int)(d.g[i][j]+(LL)a.g[i][k]*b.g[k][j])%M; 
	return d;
}


vv ksm(vv a,int x)
{
	vv c=cs;
	for(x;x>1;x>>=1)
	{
		if(x&1) c=cheng(c,a);
		vv v=cheng(a,a);
		a=v;
	}
	return cheng(a,c);
}

int main()
{
	scanf("%d%d%d%d%d",&n,&m,&t,&a,&b);
	for(i=1;i<=m+m;i++) cs.g[i][i]=1;
	for(i=1;i<=m;i++) scanf("%d%d",&s[i][0],&s[i][1]), s[i+m][0]=s[i][1], s[i+m][1]=s[i][0];
	for(i=1;i<=m+m;i++)
		for(j=1;j<=m+m;j++)
			if(s[i][1]==s[j][0] && i-j!=m && j-i!=m) f.g[i][j]=1;
	vv d=ksm(f,t-1);
	for(i=1;i<=m+m;i++)
		if(s[i][0]==a) l.g[1][i]=1;
	l=cheng(l,d);
	for(i=1;i<=m+m;i++) if(s[i][1]==b) ans=(ans+l.g[1][i])%M; 
	printf("%d",ans);
}