欢迎访问~原文出处——博客园-zhouzhendong
去博客园看该题解
题目传送门 - BZOJ1875
题意概括
在一个无向图（有重边无自环）中走，不能在经过连续经过某一条边2次。
现在走t步，问有多少中从A到B的方案。
答案mod 45989
点数<=20,边数<=60，t<=230
题解
一开始没看到不能来回走这一个条件，所以还以为是一道水题。
发现这个之后，思考一下，发现还是一道水题。
如果没有这个限制条件，那么我们按照点构建矩阵，用快速幂优化就可以了。
但是有了这个之后就稍微难一些。
我们发现边数很少，所以我们从边开始考虑。
我们发现可以按照边构建矩阵，表示从某条边到某条边的方案数。
这样可以避免来回。
边数=60*2=120，1203*log(230)可以过去的。
代码
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <cstdlib>
#include <cmath>
using namespace std;
const int N=20+5,M=60*2+5,mod=45989;
int n,m,t,A,B;
struct Gragh{
int cnt,x[M],y[M],nxt[M],fst[N];
void set(){
cnt=0;
memset(fst,0,sizeof fst);
}
void add(int a,int b){
x[++cnt]=a,y[cnt]=b,nxt[cnt]=fst[a],fst[a]=cnt;
}
}g;
struct Mat{
int v[M][M];
void set(int x){
memset(v,0,sizeof v);
if (x!=1)
return;
for (int i=1;i<=m;i++)
v[i][i]=1;
}
Mat operator * (Mat x){
Mat ans;
ans.set(0);
for (int i=1;i<=m;i++)
for (int j=1;j<=m;j++)
for (int k=1;k<=m;k++)
ans.v[i][j]=(ans.v[i][j]+v[i][k]*x.v[k][j])%mod;
return ans;
}
}M0,M1,M2,M3;
Mat MatPow(Mat x,int y){
Mat ans,now=x;
ans.set(1);
while (y){
if (y&1)
ans=ans*now;
now=now*now;
y>>=1;
}
return ans;
}
int op(int x){
if (x%2==0)
return x-1;
return x+1;
}
int main(){
scanf("%d%d%d%d%d",&n,&m,&t,&A,&B);
g.set();
for (int i=1,a,b;i<=m;i++){
scanf("%d%d",&a,&b);
g.add(a,b),g.add(b,a);
}
m<<=1;
M0.set(0);
for (int i=1;i<=m;i++){
for (int j=g.fst[g.y[i]];j;j=g.nxt[j])
if (j!=op(i))
M0.v[i][j]++;
}
M1.set(0);
for (int i=g.fst[A];i;i=g.nxt[i])
M1.v[1][i]++;
M2=MatPow(M0,t-1);
M3=M1*M2;
int ans=0;
for (int i=1;i<=m;i++)
if (g.y[i]==B)
ans=(ans+M3.v[1][i])%mod;
printf("%d",ans);
return 0;
}