【BZOJ】1875: [SDOI2009]HH去散步

题目链接：http://www.lydsy.com/JudgeOnline/problem.php?id=1875

---

注意的是路径不可以重复，所以这题把边看成点。每一条无向边拆成两条有向边。

令${F[t][i][j]}$表示从编号为$i$的边走到编号为$j$的边走了$t$步的边集个数。

${F[t][i][j]=\sum f[i-1][i][k]*f[i-1][k][j]}$

这不就是矩乘的形式么，矩乘优化DP即可。

---

 #include<iostream>

 #include<cstdio>

 #include<algorithm>

 #include<vector>

 #include<cstdlib>

 #include<cmath>

 #include<cstring>

 using namespace std;

 #define maxn 10010

 #define llg long long

 #define SIZE 126

 #define mod 45989

 #define yyj(a) freopen(a".in","r",stdin),freopen(a".out","w",stdout);

 llg nn,m,A,B,last[maxn*],t;

 llg cnt=;

 struct MATRIX

 {

       llg mt[SIZE][SIZE];

       llg x,y;

     void init(){memset(mt,,sizeof(mt)); x=y=;}

 }ans,def;

 struct edge

 {

     llg from,to,next,v;

 }e[maxn*];

 llg in_()

 {

     int x=,f=;char ch=getchar();

     while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}

     while(ch>=''&&ch<=''){x=x*+ch-'';ch=getchar();}

     return x*f;

 }

 inline MATRIX operator *(MATRIX a,MATRIX b)

 {

     MATRIX c;

     for (llg i=;i<=cnt;i++) for (llg j=;j<=cnt;j++) c.mt[i][j]=;

     c.x=a.x; c.y=b.y;

     for(int i=;i<=a.x;i++)

         for(int j=;j<=b.y;j++)

             for(int k=;k<=a.y;k++)

                 c.mt[i][j]=(c.mt[i][j]+(a.mt[i][k])*(b.mt[k][j]))%mod;

     return c;

 }

 void insert(llg v,llg u)

 {

     e[++cnt].to=v; e[cnt].from=u; e[cnt].next=last[u],last[u]=cnt;

     e[++cnt].to=u; e[cnt].from=v; e[cnt].next=last[v],last[v]=cnt;

 }

 int main()

 {

     yyj("bzoj1875");

     cin>>nn>>m>>t>>A>>B;

     for (llg i=;i<=m;i++) insert(in_(),in_());

     MATRIX b;

     b.init();

     def.x=def.y=ans.x=ans.y=b.x=b.y=cnt;

     t--;

     for (llg i=;i<=cnt;i++)

         for (llg j=;j<=cnt;j++)

             if (e[i].to==e[j].from && i!=(j^)) b.mt[i][j]++;

     for (llg i=;i<=cnt;i++) ans.mt[i][i]=;

     for (llg i=t;i;i>>=,b=b*b)

         if (i&)

             ans=ans*b;

     for (llg i=last[A];i;i=e[i].next) def.mt[][i]++;

     ans=def*ans;

     llg sum=;

     for (llg i=last[B];i;i=e[i].next) sum+=ans.mt[][i^];

     cout<<sum%mod;

     return ;

 }