bzoj 1875 [SDOI2009]HH去散步（矩乘）

Description

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

Input

第一行：五个整数N，M，t，A，B。其中N表示学校里的路口的个数，M表示学校里的路的条数，t表示HH想要散步的距离，A表示散步的出发点，而B则表示散步的终点。接下来M行，每行一组Ai，Bi，表示从路口Ai到路口Bi有一条路。数据保证Ai = Bi，但不保证任意两个路口之间至多只有一条路相连接。路口编号从0到N − 1。同一行内所有数据均由一个空格隔开，行首行尾没有多余空格。没有多余空行。答案模45989。

Output

一行，表示答案。

Sample Input

4 5 3 0 0
0 1
0 2
0 3
2 1
3 2

Sample Output

HINT

对于30%的数据，N ≤ 4，M ≤ 10，t ≤ 10。
对于100%的数据，N ≤ 20，M ≤ 60，t ≤ 230，0 ≤ A,B

【思路】

矩阵乘法，边点互换

题目中有不能走回头路的要求但同时存在重边。边点互换一下就可以满足这个要求啦。按照边的连接构造A矩阵并求出A^(t-1)，新建一个虚拟节点，使之向a的所有出边连通，B*A即可求出虚拟节点到各边长度为t的路径数，然后统计所有与b相连的边。

【代码】

 #include<cmath>

 #include<queue>

 #include<vector>

 #include<cstdio>

 #include<cstring>

 #include<iostream>

 #include<algorithm>

 #define FOR(a,b,c) for(int a=(b);a<=(c);a++)

 using namespace std;

 const int maxn = *;

 const int MOD = ;

 struct Edge { int v,next;

 }es[maxn<<];

 struct Matrix {

     int r,c,N[maxn][maxn];

     void init(int r,int c) {

         this->r=r,this->c=c;

         memset(N,,sizeof(N));

     }

     Matrix operator * (const Matrix B) const{

         Matrix C; C.init(r,B.c);

         for(int i=;i<r;i++)

             for(int j=;j<B.c;j++)

                 for(int k=;k<c;k++)

                     C.N[i][j]=(C.N[i][j]+N[i][k]*B.N[k][j])%MOD;

         return C;

     }

     Matrix pow(int p) {

         Matrix tmp=*this,ans;

         ans.init(r,r);

         for(int i=;i<r;i++) ans.N[i][i]=;

         while(p) {

             if(p&) ans=ans*tmp;

             tmp=tmp*tmp; p>>=;

         }

         return ans;

     }

 }A,B;

 int n,m,t,a,b,u,v;

 int front[maxn],en=-;

 void adde(int u,int v) {

     en++; es[en].next=front[u]; es[en].v=v; front[u]=en;

 }

 int main() {

     freopen("in.in","r",stdin);

     freopen("out.out","w",stdout);

     memset(front,-,sizeof(front));

     scanf("%d%d%d%d%d",&n,&m,&t,&a,&b);

     for(int i=;i<m;i++) {

         scanf("%d%d",&u,&v);

         adde(u,v),adde(v,u);

     }

     en+=;

     A.init(en,en),B.init(en,en);

     for(int i=front[a];i>=;i=es[i].next) B.N[en-][i]=;

     for(int i=;i<n;i++) {

         for(int u=front[i];u>=;u=es[u].next) {

             int j=es[u].v;

             for(int v=front[j];v>=;v=es[v].next)

                 if(u!=(v^))  A.N[u][v]++;

         }

     }

     A=A.pow(t-);

     A=B*A;

     int ans=;

     for(int i=front[b];i>=;i=es[i].next)

         ans=(ans+A.N[en-][i^])%MOD;

     printf("%d",ans);

     return ;

 }

秒客网