BZOJ 1875 【SDOI2009】 HH去散步

题目链接：HH去散步

　　如果不考虑不能走上一次走的边的话，这道题就是一个矩乘的裸题。

　　现在有了这个条件其实也很好做。我们平常的矩阵都是按点建的，\(A_{i,j}\)表示从第\(i\)个点走到第\(j\)个点的方案数；这里把每条边拆成两条有向边，按边建立矩阵，\(A_{i,j}\)表示第\(i\)条边走到第\(j\)条边的方案数，然后直接矩乘即可。

　　下面贴代码：

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<cmath>

#define File(s) freopen(s".in","r",stdin),freopen(s".out","w",stdout)

#define mod 45989

#define M 120

using namespace std;

typedef long long llg;

int n,m,t,a,b,s[M][2],ans;

struct Matrix{

	int w[M][M];

	Matrix(){memset(w,0,sizeof(w));}

	int* operator [] (int x){return w[x];}

	Matrix operator * (Matrix h){

		Matrix c;

		for(int i=0;i<m;i++)

			for(int j=0;j<m;j++)

				for(int k=0;k<m;k++){

					c.w[i][j]+=w[i][k]*h.w[k][j];

					if(c.w[i][j]>=mod) c.w[i][j]%=mod;

				}

		return c;

	}

}A,B;

int getint(){

	int w=0;bool q=0;

	char c=getchar();

	while((c>'9'||c<'0')&&c!='-') c=getchar();

	if(c=='-') c=getchar(),q=1;

	while(c>='0'&&c<='9') w=w*10+c-'0',c=getchar();

	return q?-w:w;

}

bool pd(int x,int y,int a=-1){

	if(a!=-1) return (s[x][0]==a || s[x][1]==a);

	for(int i=0;i<2;i++)

		for(int j=0;j<2;j++)

			if(s[x][i]==s[y][j]) return 1;

	return 0;

}

int main(){

	File("a");

	scanf("%d %d %d %d %d",&n,&m,&t,&a,&b); m<<=1;

	for(int i=0;i<m;i+=2){

		scanf("%d %d",&s[i][0],&s[i][1]);

		s[i+1][1]=s[i][0],s[i+1][0]=s[i][1];

	}

	for(int i=0;i<m;i++)

		for(int j=0;j<m;j++)

			if(i!=j && (i^j)!=1)

				if(s[i][1]==s[j][0]) A[i][j]=1;

	for(int i=0;i<m;i++) B[i][i]=1; t--;

	while(t){ if(t&1) B=B*A; A=A*A; t>>=1; }

	for(int i=0;i<m;i++) if(s[i][0]==a)

		for(int j=0;j<m;j++) if(s[j][1]==b)

			ans+=B[i][j],ans%=mod;

	printf("%d",ans);

	return 0;

}