HIT 2255 Not Fibonacci(矩阵乘法)

HIT 2255 Not Fibonacci(矩阵乘法)

题目：​​Fibonacci

Submitted : 543, Accepted

fishcanfly

The definition of fibonacci number is:

f(0) = 0, f(1) = 1, and for n>=2, f(n) = f(n - 1) + f(n - 2)

We define the new series of numbers as below:

f(0) = a, f(1) = b, and for n>=2, f(n) = p*f(n - 1) + q*f(n - 2),where p and q

s-th element to the e-th element, that is, to calculate

.""""

Great!Let's go!

Input

t (1 <= t <= 30), the number of test cases, followed by the input data for each test case.

6 integers a,b,p,q,s,e as concerned above. We know that -1000 <= a,b <= 1000,-10 <= p,q <= 10 and 0 <= s <= e <= 2147483647.

Output

S MOD (10^7) in the range [0,10^7)

Sample Input

20 1 1 -1 0 3 0 1 1 1 2 3

Sample Output

23

Hint: You should not use int/long when it comes to an integer bigger than  2147483647.

陷阱：a,b可能为负数。

#include #include using namespace std;const int mod=1e7;typedef long long LL;struct matrie{ LL m[3][3];};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+mod)%mod; b.m[k][j]=(b.m[k][j]%mod+mod)%mod; c.m[i][j]=c.m[i][j]+a.m[i][k]*b.m[k][j]%mod; } c.m[i][j]%=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); LL n; LL a,b,p,q,s,e; cin>>n; while(n--){ cin>>a>>b>>p>>q>>s>>e; LL q1,q2; matrie A={ p,q,0, 1,0,0, p,q,1 }; if(s==0) q1=0; else if(s==1) q1=(a+mod)%mod; else if(s==2) q1=(a%mod+b%mod+mod)%mod; else if(s>2){ matrie qs1=power(A,s-2); q1=(qs1.m[2][0]*b%mod+qs1.m[2][1]*a%mod+qs1.m[2][2]*(a+b)%mod)%mod; } if(e==0) q2=(a%mod+mod)%mod; else if(e==1) q2=(a%mod+b%mod+mod)%mod; else if(e>1){ matrie qs2=power(A,e-1); q2=(qs2.m[2][0]*b%mod+qs2.m[2][1]*a%mod+qs2.m[2][2]*(a+b)%mod)%mod; } //cout<

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