hdu 2254（矩阵）-白红宇

hdu 2254（矩阵）

阅读量：6961 次

发布时间：2019-06-27

本文共 1196 字，大约阅读时间需要 3 分钟。

题意：指定v1，v2，要求计算出在t1,t2天内从v1->v2的走法

思路：可以知道由矩阵求，即将其建图A，求矩阵A^t1 + ...... + A^t2. A^n后，/*A.xmap[v1][v2]即是从v1到v2要n步

所以先预处理出A^1 -A^10000的情况,后面再注意下细节，计算即可.

(每条道路走需要花一天的时间，且不能在某个城市停留,且t1=0时的走法数为0)

开始以为只要t1 = 0就输出0，结果不停WA,一直对照别人的代码- -

结果偶然发现这个特例，它喵的我也是醉了，才发现是题意理解错了，好惨...Orz

特例：

Input:

1 1 0 1

Ouput:

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            #include
             
              #include
              
               #include
               
                #include
                
                 #include
                 
                  using namespace std;typedef long long ll;const int mod=2008;const int maxn=5e5;map
                  
                   has;struct Maxtri{ int xmap[30][30];};int siz;Maxtri mat[10005];Maxtri Mul(Maxtri &a,Maxtri &b){ Maxtri c; for(int i=0; i
                   
                     t2) swap(t1,t2); int ans=0; for(int i=t1-1; i