hdu2254 奥运
题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=2254
题意:题目让我们求得是的可以得到的金牌数量,而和金牌数量=在t1到t2天(包括t1,t2)内从v1到v2共有多少种走法,每天走一步。这个题的坑在于如果v1或者v2城市不存在,还有t1>t2这两种情况都是不可能的,所以直接输出答案为0。
对于题目给我们数据,我们首先需要离散化建图。这里说一下,邻接矩阵我认为可以把它叫做一步可达矩阵,也就是说我们建立一个邻接矩阵,可以直接用M[a][b]看出走一步就可以完成a到b的路线有多少条路线。然后如果将这个矩阵自乘一次就可以得到两步到达可以完成从a到b的路线有多少条路,再乘一次就是可以得到三步可以从a到b的路线有多少条,以此类推,所以对于这道题,我们只需要把走一天和走一万天的矩阵都算出来。然后对于每次查询,我们线性相加就好了。具体看代码……这道题算是学到一个矩阵的姿势了。
//Author: xiaowuga #include<iostream> #include<map> #include<cstring> #define maxx INT_MAX #define minn INT_MIN #define inf 0x3f3f3f3f #define size 31 #define mod 2008 using namespace std; typedef long long ll; map<int,int>li; int ct=0; struct Mat{ int mat[size][size]; void clear(){ memset(mat,0,sizeof(mat)); } Mat operator *(const Mat &m) const{ Mat tmp; tmp.clear(); for(int k=0;k<ct;k++) for(int i=0;i<ct;i++){ if(mat[i][k]==0) continue; for(int j=0;j<ct;j++){ if(m.mat[k][j]==0) continue; tmp.mat[i][j]+=mat[i][k]*m.mat[k][j]%mod; tmp.mat[i][j]%=mod; } } return tmp; } }M[10000]; int main(){ ios::sync_with_stdio(false);cin.tie(0); int n; while(cin>>n){ li.clear(); ct=1; int a,b; Mat m; m.clear(); for(int i=0;i<n;i++){ cin>>a>>b; if(li.count(a)==0) li[a]=ct++;a=li[a]; if(li.count(b)==0) li[b]=ct++;b=li[b]; m.mat[a][b]++; } M[1]=m; for(int i=2;i<10000;i++) M[i]=M[i-1]*m; int T,v1,v2,t1,t2; cin>>T; while(T--){ cin>>v1>>v2>>t1>>t2; if(t1>t2||t2==0){ cout<<0<<endl;continue; } int x=-1,y=-1; if(li.count(v1)!=0) x=li[v1]; if(li.count(v2)!=0) y=li[v2]; if(x==-1||y==-1){ cout<<0<<endl;continue; } ll sum=0; for(int i=t1;i<=t2;i++){ if(i==0) continue; sum+=M[i].mat[x][y]%mod; sum%=mod; } cout<<sum<<endl; } } return 0; }