P2151 [SDOI2009]HH去散步

Aimee

首先的问题，如果这个题是无向图怎么搞，显然dp[i][j]表示到点i走了j步就可以了。

但是这是无向图啊，怎么搞呢

那就统计一下从那条边来的，也就是i表示从i边结束

然后暴力转移显然，但是tle起飞

显然可以用矩阵优化一下。

下标很重要，因为矩阵乘法的美妙性质。

最后的统计的时候正难则反，统计反向的边。

结构体是个好东西，妥善利用起来，还有重载，减少码量。

更详细的题解

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
int n,m,t,S,T;
int mod=45989;
int x,y;
struct edge{
	int to;
	int f;
	int ne;
}ed[150];
int head[60];
int p=0;
int ans[160][160];
int l;
int tem[160][160];
int fa[160][160];
int org[160][160];
void power(int n){
	while(n){
		if(n&1){
			for(int i=1;i<=l;++i){
				for(int j=1;j<=l;++j){
					tem[i][j]=0;
					for(int k=1;k<=l;++k){
						tem[i][j]+=org[i][k]*ans[k][j];
						tem[i][j]%=mod;
					}
				}
			}
			for(int i=1;i<=l;++i){
				for(int j=1;j<=l;++j){
					ans[i][j]=tem[i][j];
				}
			}
		}
		n>>=1;
		for(int i=1;i<=l;++i){
			for(int j=1;j<=l;++j){
				tem[i][j]=0;
				for(int k=1;k<=l;++k){
					tem[i][j]+=org[i][k]*org[k][j];
					tem[i][j]%=mod;
				}
			}
		}
		for(int i=1;i<=l;++i){
			for(int j=1;j<=l;++j){
				org[i][j]=tem[i][j];
			}
		}
	}
	return ;
}
int op(int x){
	return (x&1) ?x+1:x-1;
}
int znx;
void add(int f,int to){
	ed[++p].f=f;
	ed[p].to=to;
	ed[p].ne=head[f];
	head[f]=p;
}
signed main(){
	scanf("%d%d%d%d%d",&n,&m,&t,&S,&T);
	S++;
	T++;
	for(int i=1;i<=m;++i){
		scanf("%d%d",&x,&y);
		x++;
		y++;
		add(x,y);
		add(y,x);
	}
	for(int i=1;i<=p;++i){
		for(int  k=head[ed[i].to];k;k=ed[k].ne){
			if(k!=op(i)){
				org[k][i]++;
			}
		}	
	}
	l=p;
	for(int i=1;i<=p;++i){
		ans[i][i]=1;
	}
	for(int i=head[S];i;i=ed[i].ne){
		fa[i][1]++;
	}
	power(t-1);
	for(int i=1;i<=l;++i){
			for(int j=1;j<=l;++j){
				tem[i][j]=0;
				for(int k=1;k<=l;++k){
					tem[i][j]+=ans[i][k]*fa[k][j];
					tem[i][j]%=mod;
				}
			}
		}
	for(int i=head[T];i;i=ed[i].ne){
		znx=(znx+tem[op(i)][1])%45989;
	}
	cout<<znx;
	return 0;
}