BZOJ 1875 [SDOI2009]HH去散步

题目大意

给你一个无向图，你在这张图里行走，不可以连续两次走同一条路（走过去再走回来），求走t步(每条边为1步)从a到b的行进路线个数。

这题很令人懵逼……本来是一个很简单的矩阵乘法优化DP但是在加入了“不允许连续两次走过同一条边”之后就很懵逼了……

考虑是边和边之间的关系，考虑化点为边。我们把双向边拆成两条，设$F_{i,j}$表示走了i条边，最后一条走过的边是j号边的方案个数，此时有 $F_{i,j} = \sum \limits_{k}^{k \to j} F_{i-1,k}$ ( $k \to j$ 表示k的终点是j的起点且k和j不是同一条边的两个方向)

之后初始化GG，去重特判GG，各种GG让我心如潮水= =真是GG

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define N 400
#define MO 45989
int n,m,t,a,b,ix,iy,u[N],v[N],s[N][N],ta[N][N],f[N],tb[N],ckh;
void calc()
{
    memset(tb,0,sizeof tb);
    for(int i=1;i<=m;++i)
        for(int j=1;j<=m;++j)
            tb[i]=(tb[i]+f[j]*s[j][i])%MO;
    memcpy(f,tb,sizeof tb);
}
void mul()
{
    memset(ta,0,sizeof ta);
    for(int i=1;i<=m;++i)
        for(int j=1;j<=m;++j)
            for(int k=1;k<=m;++k)
                ta[i][j]=(ta[i][j]+s[i][k]*s[k][j])%MO;
    memcpy(s,ta,sizeof ta);
}
int main()
{
    scanf("%d%d%d%d%d",&n,&m,&t,&a,&b),a++,b++,t++;
    for(int i=1;i<=m;++i) scanf("%d%d",u+i,v+i),u[i]++,v[i]++,u[i+m]=v[i],v[i+m]=u[i];
    ckh=m;
    m<<=1;
    for(int i=1;i<=m;++i) for(int j=1;j<=m;++j) 
        if(abs(i-j)!=ckh&&v[i]==u[j]) s[i][j]=1;
    f[m+1]=1;
    for(int i=1;i<=m;++i)
    {
        if(u[i]==a) s[m+1][i]=1;
        if(v[i]==b) s[i][m+2]=1;
    }
    m+=2;
    for(int i=0;(1ll<<i)<=t;++i)
    {
        if((1ll<<i)&t) calc();
        mul();
    }
    printf("%d\n",f[m]);
    return 0;
}