HIT 2060 Fibonacci Problem Again(矩阵乘法)

HIT 2060 Fibonacci Problem Again(矩阵乘法)

题目：​​Problem Again

Submitted : 547, Accepted

As we know , the Fibonacci numbers are defined as follows:

"""" Given two numbers a and b , calculate

. """"

Input

The input contains several test cases. Each test case consists of two non-negative integer numbers a and b (0 ≤ a ≤ b ≤1,000,000,000). Input is terminated by a = b = 0.

Output

For each test case, output S mod 1,000,000,000, since S may be quite large.

Sample Input

1 13 5 10 1000 0 0

Sample Output

116 496035733

关于取模的问题每步都要注意啊！！

#include #include using namespace std;const int mod=1e9;typedef long long LL;struct matrie{ LL m[3][3];};matrie A={ 1,1,0, 1,0,0, 1,1,1};matrie I={ 1,0,0, 0,1,0, 0,0,1};matrie multi(matrie a,matrie b){ matrie c; for(LL i=0;i<3;i++){ for(LL j=0;j<3;j++){ c.m[i][j]=0; for(LL k=0;k<3;k++){ a.m[i][k]=a.m[i][k]%mod; b.m[k][j]=b.m[k][j]%mod; c.m[i][j]=(c.m[i][j]+a.m[i][k]*b.m[k][j]%mod)%mod; } } } return c;}matrie power(matrie a,LL k){ matrie ans=I,tmp=a; while(k){ if(k&1)ans=multi(ans,tmp); tmp=multi(tmp,tmp); k>>=1; } return ans;}int main(){ //freopen("cin.txt","r",stdin); int a,b; while(cin>>a>>b){ if(a==0&&b==0) break; LL q1,q2; if(a==0) q1=0; else if(a==1) q1=1; else if(a==2) q1=2; else if(a>2){ matrie qs1=power(A,a-2); q1=(qs1.m[2][0]*1%mod+qs1.m[2][1]*1%mod+qs1.m[2][2]*2%mod)%mod; } if(b==0) q2=1; else if(b==1) q2=2; else if(b>1){ matrie qs2=power(A,b-1); q2=(qs2.m[2][0]*1%mod+qs2.m[2][1]*1%mod+qs2.m[2][2]*2%mod)%mod; } LL ans=(q2-q1+mod)%mod; cout<

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。