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 Description
北京迎来了第一个奥运会,我们的欢呼声响彻中国大地,所以今年的奥运金牌 day day up!
比尔盖兹坐上鸟巢里,手里摇着小纸扇,看的不亦乐乎,被俺们健儿的顽强拼搏的精神深深的感动了。反正我的钱也多的没地方放了,他对自己说,我自己也来举办一个奥运会,看谁的更火。不过他的奥运会很特别:
1 参加人员必须是中国人;
2 至少会加法运算(因为要计算本人获得的金牌数)
他知道中国有很多的名胜古迹,他知道自己在t1 到 t2天内不可能把所有的地方都玩遍,所以他决定指定两个地方v1,v2,如果参赛员能计算出在t1到t2天(包括t1,t2)内从v1到v2共有多少种走法(每条道路走需要花一天的时间,且不能在某个城市停留,且t1=0时的走法数为0),那么他就会获得相应数量的金牌,城市的总数<=30,两个城市间可以有多条道路
,每条都视为是不同的。
比尔盖兹坐上鸟巢里,手里摇着小纸扇,看的不亦乐乎,被俺们健儿的顽强拼搏的精神深深的感动了。反正我的钱也多的没地方放了,他对自己说,我自己也来举办一个奥运会,看谁的更火。不过他的奥运会很特别:
1 参加人员必须是中国人;
2 至少会加法运算(因为要计算本人获得的金牌数)
他知道中国有很多的名胜古迹,他知道自己在t1 到 t2天内不可能把所有的地方都玩遍,所以他决定指定两个地方v1,v2,如果参赛员能计算出在t1到t2天(包括t1,t2)内从v1到v2共有多少种走法(每条道路走需要花一天的时间,且不能在某个城市停留,且t1=0时的走法数为0),那么他就会获得相应数量的金牌,城市的总数<=30,两个城市间可以有多条道路
,每条都视为是不同的。
Input
本题多个case,每个case:
输入一个数字n表示有n条道路 0<n<10000
接下来n行每行读入两个数字 p1,p2 表示城市p1到p2有道路,并不表示p2到p1有道路 (0<=p1,p2<2^32)
输入一个数字k表示有k个参赛人员
接下来k行,每行读入四个数据v1,v2,t1,t2 (0<=t1,t2<10000)
输入一个数字n表示有n条道路 0<n<10000
接下来n行每行读入两个数字 p1,p2 表示城市p1到p2有道路,并不表示p2到p1有道路 (0<=p1,p2<2^32)
输入一个数字k表示有k个参赛人员
接下来k行,每行读入四个数据v1,v2,t1,t2 (0<=t1,t2<10000)
Output
对于每组数据中的每个参赛人员输出一个整数表示他获得的金牌数(mod 2008)
Sample Input
6 1 2 1 3 2 3 3 2 3 1 2 1 3 1 2 0 0 1 2 1 100 4 8 3 50
Sample Output
0 1506 0
Source
Recommend
lcy
#include<stdio.h> #include<string.h> #include<map> using namespace std; #define ll int #define mod 2008 struct 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