[JZOJ1088]【SDOI2009】HH去散步

Description

HH有个一成不变的习惯，喜欢饭后百步走。所谓百步走，就是散步，就是在一定的时间 内，走过一定的距离。 但是同时HH又是个喜欢变化的人，所以他不会立刻沿着刚刚走来的路走回。 又因为HH是个喜欢变化的人，所以他每天走过的路径都不完全一样，他想知道他究竟有多 少种散步的方法。 现在给你学校的地图（假设每条路的长度都是一样的都是1），问长度为t，从给定地 点A走到给定地点B共有多少条符合条件的路径。

Solution

经典的矩阵乘法路径数问题

但是加了一个限制，就是不能走刚走过的路。

原来的邻接矩阵就不能用了

先将边拆成有向的 考虑将点与点间转移转化成边与边转移 将原先邻接矩阵 a[i][j] 转化成 b[i][j] 表示从第 i 条边的起点走到第j条边的起点的方案数

然后原来从一条无向边之间拆出来的两条有向边之间不连即可。

Code

#include <cstdio> #include <cstdlib> #include <algorithm> #include <iostream> #include <cstring> #include <cmath> #define fo(i,a,b) for(int i=a;i<=b;i++) #define fod(i,a,b) for(int i=a;i>=b;i--) #define N 22 #define M 122 #define mo 45989 using namespace std; int n,m,t,st,ed,al[2*M][2],fr[N][2*M]; struct node { int a[M][M]; }; node ti(node a,node b) { node c; fo(i,1,2*m) fo(j,1,2*m) { c.a[i][j]=0; fo(k,1,2*m) c.a[i][j]=(c.a[i][j]+a.a[i][k]*b.a[k][j])%mo; } return c; } node s; node ksm(node k,int n) { if(n==1) return k; node s=ksm(k,n/2); return (n%2)?ti(s,ti(s,k)):ti(s,s); } int main() { cin>>n>>m>>t>>st>>ed; fo(i,1,m) { int x,y; scanf("%d%d",&x,&y); al[2*i-1][0]=al[2*i][1]=x; al[2*i-1][1]=al[2*i][0]=y; fr[x][++fr[x][0]]=2*i-1; fr[y][++fr[y][0]]=2*i; } fo(i,1,2*m) { int x=al[i][0],y=al[i][1]; fo(j,1,fr[y][0]) { if(abs(fr[y][j]/2-i/2)==1&&abs(fr[y][j]-i)==1) continue; s.a[i][fr[y][j]]=1; } } s=ksm(s,t-1); int ans=0; fo(i,1,2*m) { fo(j,1,2*m) { if(al[i][0]==st&&al[j][1]==ed) ans=(ans+s.a[i][j])%mo; } } cout<<ans; }