hdu 2254 不错的矩阵 从a到b 在规定时间内有多少条路到达

http://acm.hdu.edu.cn/showproblem.php?pid=2254

奥运Time Limit: 1000/1000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 1629    Accepted Submission(s): 393


Problem DescriptionInputOutputSample InputSample OutputSourceRecommend#include<stdio.h>#include<string.h>#include<map>using namespace std; #define ll int#define mod 2008struct Mat{ll martix[30][30];};Mat temp,q,p,res,init,mid1,mid2;ll N;Mat Martix_Add(Mat a,Mat b) { ll i,j; Mat c; for (i=0;i<N;i++) { for (j=0;j<N;j++) { c.martix[i][j]=(a.martix[i][j]+b.martix[i][j])%mod; } } return c; } Mat Martix_Mul(Mat a,Mat b) { ll i,j,l; Mat c; for (i=0;i<N;i++) { for (j=0;j<N;j++) { c.martix[i][j]=0; for (l=0;l<N;l++) { c.martix[i][j]+=(a.martix[i][l]*b.martix[l][j])%mod; c.martix[i][j]%=mod; } } } return c; } Mat er_fun(Mat e,ll x) //求矩阵e^x { Mat tp; tp=e; e=res; //res是单位矩阵 while(x) { if(x&1) e=Martix_Mul(e,tp); tp=Martix_Mul(tp,tp); x>>=1; } return e; } Mat Solve(Mat a,ll p) //计算 a^1+a^2.....+a^p{ if(p==1||p==0) return a; else if(p&1) return Martix_Add(er_fun(a,p),Solve(a,p-1)); else return Martix_Mul(Solve(a,p>>1),Martix_Add(er_fun(a,p>>1),res)); } int main(){ ll n,j,i,cnt,ans; __int64 x,y; for(i=0;i<30;i++) for(j=0;j<30;j++) { if(i==j) res.martix[i][j]=1; else res.martix[i][j]=0; } while(scanf("%d",&n)!=EOF) { cnt=0; map<__int64,int>mp; memset(init.martix,0,sizeof(init.martix)); while(n--) { scanf("%I64d %I64d",&x,&y); if(mp.find(x)==mp.end()) mp[x]=cnt++; if(mp.find(y)==mp.end()) mp[y]=cnt++; init.martix[mp[x]][mp[y]]++; } N=cnt; ll m; scanf("%d",&m); while(m--) { ll t1,t2; scanf("%I64d %I64d %d %d",&x,&y,&t1,&t2); if(mp.find(x)==mp.end()||mp.find(y)==mp.end()||(t1==0&&t2==0))//注意细节 { printf("0\n"); continue; } x=mp[x]; y=mp[y]; if(t1>1) { mid1=Solve(init,t1-1); mid2=Solve(init,t2); ans=(mid2.martix[x][y]-mid1.martix[x][y])%mod; } else { mid1=Solve(init,t2); ans=mid1.martix[x][y]%mod; } if(ans<0) ans+=mod; printf("%d\n",ans); } }return 0;}//不能全用__int64 这样会栈溢出

另外 本题海可以用    矩阵连续相乘 保存 起来  Mat a[10000]  把所有得到的矩阵保存下来

hnust_xiehonghao