[SDOI2009]HH去散步

   
    时间限制: 1 Sec  
    内存限制: 64 MB
    提交: 64  
    解决: 28
[提交][状态][讨论版]
   
题目描述
   

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

    
 
    

     第一行：五个整数N，M，t，A，B。
    
    

     N表示学校里的路口的个数
    
    

     M表示学校里的 路的条数
    
    

     t表示HH想要散步的距离
    
    

     A表示散步的出发点
    
    

     B则表示散步的终点。
    
    

     接下来M行
    
    

     每行一组Ai，Bi，表示从路口Ai到路口Bi有一条路。
    
    

     数据保证Ai ！= Bi,但不保证任意两个路口之间至多只有一条路相连接。 
    
    

     路口编号从0到N -1。 
    
    

     同一行内所有数据均由一个空格隔开，行首行尾没有多余空格。没有多余空行。 
    
    

     答案模45989。
    
    

     N ≤ 20，M ≤ 60，t ≤ 2^30，0 ≤ A,B
    
    
 
   
输出
   

    
一行，表示答案。
   
样例输入

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

样例输出

4

HH散步：题解：矩阵优化dp

这道题与用图邻接矩阵G^k  G[a,b]表示a到b长度为ｋ的路径条数的思路有点类似。但是有一个附加的条件就是他不回立刻沿着刚走来的路走回，就是不能从1->2->1，但是可以1->2->3->4->2->1，只有不是连着的，路径就可以重复走。

那么这样的话肯定不能用点的邻接矩阵来表示了，所以改成用边的。

用w表示边的起点，v表示边的终点，那么如果v[i]=w[j]（注意i,j不可颠倒，因为我们把每条边都存储了双向边，所以对于现在的每一条边都是单向的），那么表示第ｉ条边可以走到第j条边，那么矩阵dis[i][j]=1。

然后用一个1*tot的矩阵表示，把所有由起点发出的边付成1，用这个1×tot的矩阵×  G^(K-1)（刚才构造的边的矩阵）

得到的一个1×tot的矩阵就表示从起点相连的边到所以边长度为k的路径数。

然后累加ans[1][连向终点的边]，就是最后的答案。

#include<iostream> #include<cmath> #include<algorithm> #include<cstdio> #include<cstdlib> #include<cstring> #include<map> #include<set> #define V 2005 usingnamespacestd; intn,m,t,sd[V][2],tt[25][25],aa,bb; set<pair<int,int> >st; ints[150],f[150][150],w[150][150],z[150][150],sr[150][150],as[150]; intk,mod=45989; voidmuti() {memset(w,0,sizeof(w));for(inti=1;i<=k;i++)for(intj=1;j<=k;j++)for(intp=1;p<=k;p++)w[i][j]=(w[i][j]+sr[i][p]*f[p][j]%mod)%mod;for(inti=1;i<=k;i++)for(intj=1;j<=k;j++)sr[i][j]=w[i][j]; } voidmuti1() {memset(z,0,sizeof(z));for(inti=1;i<=k;i++)for(intj=1;j<=k;j++)for(intp=1;p<=k;p++)z[i][j]=(z[i][j]+f[i][p]*f[p][j]%mod)%mod;for(inti=1;i<=k;i++)for(intj=1;j<=k;j++)f[i][j]=z[i][j]; } intmain() {// freopen("in.txt","r",stdin);freopen("out.txt","w",stdout);//freopen("turnover.in","r",stdin);freopen("turnover.out","w",stdout);cin>>n>>m>>t>>aa>>bb;aa++;bb++;intx,y;for(inti=1;i<=m;i++){cin>>x>>y;x++;y++;sd[i][0]=x;sd[i][1]=y;}for(inti=1+m;i<=2*m;i++){sd[i][1]=sd[i-m][0];sd[i][0]=sd[i-m][1];}k=2*m;for(inti=1;i<=k;i++)for(intj=1;j<=k;j++)if(sd[i][1]==sd[j][0]&&abs(i-j)!=m)f[i][j]=1;for(inti=1;i<=k;i++)if(sd[i][0]==aa){s[i]=1;//cout<<i<<endl;}t--; for(inti=1;i<=k;i++)sr[i][i]=1;while(t){if(t&1)muti(); muti1();t>>=1;}//for(int i=1;i<=k;i++)//for(int j=1;j<=k;j++)//cout<<sr[i][j]<<" "<<i<<" "<<j<<endl;intans=0;for(inti=1;i<=k;i++)for(intj=1;j<=k;j++)as[j]=(as[j]+s[i]*sr[i][j]%mod)%mod;for(inti=1;i<=k;i++)if(sd[i][1]==bb)ans=(ans+as[i]%mod)%mod;cout<<ans<<endl;return0; }