Not Fibonacci(矩阵连乘)

网友投稿 942 2022-08-23

Not Fibonacci(矩阵连乘)

Not Fibonacci

Not Fibonacci(矩阵连乘)


description


Maybe ACMers of HIT are always fond of fibonacci numbers, because it is so beautiful. Don't you think so? At the same time, fishcanfly always likes to change and this time he thinks about the following series of numbers which you can guess is derived from the definition of fibonacci number. 

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 are integers.

Just like the last time, we are interested in the sum of this series from the s-th element to the e-th element, that is, to calculate S(n)=f(s)+f(s+1)+...+f(e);


input


The first line of the input file contains a single integer t (1 <= t <= 30), the number of test cases, followed by the input data for each test case. 

Each test case contains 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


One line for each test case, containing a single interger denoting S MOD (10^7) in the range [0,10^7) and the leading zeros should not be printed.


sample_input


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


sample_output


2
3


hint


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


AC代码:

#include #include #include #include #include #include #include #include #include #include #include #include #include typedef long long LL; const LL maxn = 1000+10;const LL mod =10000000; using namespace std; struct matrix{ LL m[3][3];};matrix A;matrix I={ 1,0,0, 0,1,0, 0,0,1};matrix multi(matrix a,matrix b){ matrix c; for(int i=0;i<3;i++) for(int j=0;j<3;j++){ c.m[i][j]=0; for(int k=0;k<3;k++){ c.m[i][j]+=a.m[i][k]*b.m[k][j]%mod; } c.m[i][j]%=mod; } return c;}matrix power(matrix A,LL k){ matrix ans=I,p=A; while(k){ if(k&1){ ans=multi(ans,p); k--; } k>>=1; p=multi(p,p); } return ans;}int main(){ int t,a,b,p,q,s,e; scanf("%d",&t); while(t--){ scanf("%d%d%d%d%d%d",&a,&b,&p,&q,&s,&e); A.m[0][0]=1;A.m[0][1]=p;A.m[0][2]=q; A.m[1][0]=0;A.m[1][1]=p;A.m[1][2]=q; A.m[2][0]=0;A.m[2][1]=1;A.m[2][2]=0; s--; int s1,s2; if(s<0) s1=0; else if(s==0) s1=a; else{ matrix ans=power(A,s-1); s1=(ans.m[0][0]%mod*(a+b)%mod+ans.m[0][1]%mod*b%mod+ans.m[0][2]%mod*a%mod)%mod; } if(e==0) s2=a; else{ matrix ans=power(A,e-1); s2=(ans.m[0][0]%mod*(a+b)%mod+ans.m[0][1]%mod*b%mod+ans.m[0][2]%mod*a%mod)%mod; } LL l=((s2-s1)%mod+mod)%mod; cout<

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

上一篇:从架构的角度看,如何写好代码?(写代码的思路)
下一篇:HDU 2037 circumgyrate the string(字符串翻转)
相关文章

 发表评论

暂时没有评论,来抢沙发吧~