[BZOJ1975]HH去散步 图论+矩阵
题目大意
要求出在一个m条边，n个点的图中，相邻两次走的边不能相同，求在t时间时从起点A走到终点B的路径方案总数。将答案mod45989
输入格式：
第一行：五个整数N，M，t，A，B。
后面的m行，每行有两个数(a_i) (b_i)，表示路口(a_i) (b_i)有有一条边。
输出格式：
一个整数，表示答案。
输入输出样例
input
4 5 3 0 0
0 1
0 2
0 3
2 1
3 2
output
4
Hint
对于30%的数据，N ≤ 4，M ≤ 10，t ≤ 10。 对于100%的数据，N ≤ 20，M ≤ 60，t ≤ 2^30，0 ≤ A,B
解题分析
题目问你路径的方案总数，首先就想到要用矩阵＋floyd的算法来求。
我们根据floyd的原理可以知道(L[i][j]=sumlimits_{k=1}^{n}L[i][k]*L[k][j])
所以我们可以建立一个矩阵 (g[i][j])代表有一条从i到j的比。将这个矩阵幂t次，(g[i][j])就代表i到j的走t条边的方案数。
因为这一题相邻两次走的边不能相同，所以我们就将边变成点来求方案数。
那么怎么统计答案呢？我们可以有一个转移矩阵2m2m，其中(f[i][j])代表第i条边(原图中)的起点与第j条边(原图中)是一个点(且ij不能是同一条边)，就代表点(新图)i与点(新图)j是相连的。答案矩阵是一个12m的矩阵,(ans[1][i])代表第i(原图)条边的终点为题目给的A.把ans与自乘t次的F矩阵相乘。然后
$$sum ans[1][i]（i代表终点为B的点(原图的边)）$$就是答案。
其实我们可以理解为，ans就是加了一个虚点，代表着一个与所有起点为A的点(原图中的边)相连的点。乘后的ans代表这个虚点到所以点的方案。我们只要统计终点为B的点的方案数就可以了。
代码自带大常数＝＝！
#include <stdio.h>
#include <iostream>
#include <cmath>
#include <queue>
#include <algorithm>
#include <cstring>
#include <climits>
#include <cstdlib>
#define MAXN (60+10)*2
#define max(a,b) (a>b?a:b)
#define min(a,b) (a<b?a:b)
using namespace std;
int mod=45989,n,m,a,b,t,num,head[MAXN],tot,tail[MAXN],M;
struct Edge{
int next,to,from,next1;
}edge[MAXN<<1];
void add(int from,int to)
{
edge[++num].next=head[from];
edge[num].next1=tail[to];
edge[num].to=to;
edge[num].from=from;
head[from]=num;
tail[to]=num;
}
struct matrix{
int n,m;
int data[MAXN][MAXN];
void print()
{
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
printf("%d ",data[i][j]);
printf("
");
}
}
matrix operator * (matrix b)
{
matrix ans;
memset(ans.data,0,sizeof(ans.data));
ans.n=n;ans.m=b.m;
for(int i=1;i<=ans.n;i++)
for(int j=1;j<=ans.m;j++)
for(int k=1;k<=ans.m;k++)
ans.data[i][j]+=(data[i][k]*b.data[k][j])%mod,ans.data[i][j]%=mod;
return ans;
}
void too(matrix b)
{
n=b.n;m=b.m;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
data[i][j]=b.data[i][j];
}
}f,ans,zero,pf;
void power(int k)
{
if(k==1) pf=f;
else
{
power(k/2);
if(k%2==1) pf=pf*pf,pf=pf*f;
else pf=pf*pf;
}
}
int main()
{
scanf("%d%d%d%d%d",&n,&m,&t,&a,&b);
for(int i=1;i<=m;i++)
{
int x,y;
scanf("%d%d",&x,&y);
add(x,y);
add(y,x);
}
f.n=f.m=2*m;ans.n=1;ans.m=2*m;M=2*m;
for(int i=head[a];i;i=edge[i].next) ans.data[1][i]=1;
for(int s=0;s<n;s++)
for(int i=head[s];i;i=edge[i].next)
for(int j=head[edge[i].to];j;j=edge[j].next)
if((i+1)!=((j+1)^1))
{
f.data[i][j]++;
}
power(t-1);ans=ans*pf;
for(int i=tail[b];i;i=edge[i].next1)
tot=(tot+ans.data[1][i])%mod;
printf("%d
",tot);
return 0;
}