P2151 [SDOI2009] HH去散步 题解
传送门
简要题意：有\(n\)个人，\(m\)条无向边，走\(e\)条边，满足条件若第\(i\)条边为\(u->v\)则第\(i+1\)条边不能是\(v->u\)，问\(s->t\)的方案有多少个，取模45989。
因为要满足题目关于边的条件，所以我们考虑点边互换。
将\(u-v\)的无向边一分为二变成\(u->v,v->u\)，第\(i\)条边记录两个变量为\(i.from,i.to\)，表示\(i\)从\(i.from\)到\(i.to\)的边，他们互为反边。
则从第\(i\)条边走到第\(j\)条边的条件是\(i.to=j.from\)
先考虑用动态规划思考转移方程：
\(f_{i,j}\)表示第\(i\)个时刻走到第\(j\)条边的方案
\(f_{i,j}=\sum\limits_{k=1}^{2m}f_{i-1,k}*a_{k,j}\)，其中若第\(k\)条边可以走到第\(j\)条边则\(a_{k,j}=1\),否则为\(0\)。
因为\(e\)很大，所以我们要考虑矩阵乘法
构造转移矩阵\(B\)满足\(B_{i,j}\)表示第\(i\)条边到第\(j\)条边的方案。则\(B_{i,j}=1\)的情况为\(i.to=j.from\)且\(i\)与\(j\)不能互为反边
构造初始矩阵\(A\)，\(A_{i,j}\)表示第\(i\)条边到第\(j\)条边的方案。则\(A_{i,j}=1\)的条件时\(i.to=j.from=s\)，注意这里有个细节，因为我们是从\(s\)点而不是走某一条边开始走，所以我们不分正反边且只需枚举一个\(i.to=s\)的情况表示从\(s\)开始走即可。
若\(Ans_{i,j}\)表示最终从第i条边走到第\(j\)条边的方案数。如果\(i.to=s\)且\(j.to=t\)，则\(ans+=Ans_{i,j}\)
上代码：
#include<bits/stdc++.h>
#define ll long long
#define PLL pair<ll,ll>
using namespace std;
const ll M=130,mod=45989;
ll n,m,ti,s,t,flag;
ll u,v,idx,ans;
struct fu
{
ll from,to;
}bian[200];
struct jgt
{
ll a[M][M];
}A,B;
jgt operator * (const jgt t1,const jgt t2)
{
jgt t={0};
for(ll i=0;i<=idx;i++)
for(ll j=0;j<=idx;j++)
for(ll k=0;k<=idx;k++)
t.a[i][j]=(t.a[i][j]+(t1.a[i][k]*t2.a[k][j])%mod)%mod;
return t;
}
void sc(jgt t1)
{
printf("输出：\n");
for(ll i=0;i<=idx;i++)
{
for(ll j=0;j<=idx;j++)
printf("%lld ",t1.a[i][j]);
printf("\n");
}
printf("输出完毕！\n");
}
int main()
{
scanf("%lld %lld %lld %lld %lld",&n,&m,&ti,&s,&t);
for(ll i=1;i<=m;i++)
{
scanf("%lld %lld",&u,&v);
bian[idx++]={u,v};
bian[idx++]={v,u};
}
idx--,ti--;
for(ll i=0;i<=idx;i++)
for(ll j=0;j<=idx;j++)
if(bian[i].to==bian[j].from&&j!=i&&j!=(i^1)) B.a[i][j]=1;
for(ll i=0;i<=idx;i++)
{
for(ll j=0;j<=idx;j++)
if(bian[i].to==bian[j].from&&bian[j].from==s) A.a[i][j]=1;
if(bian[i].to==s)
{
flag=i;
break;
}
}
while(ti)
{
if(ti&1) A=A*B;
B=B*B;
ti=ti/2;
}
for(ll j=0;j<=idx;j++)
if(bian[j].to==t) ans=(ans+A.a[flag][j])%mod;
printf("%lld\n",ans);
return 0;
}