【矩阵快速幂】UVA 10698 G - Yet another Number Sequence

【矩阵快速幂】UVA 10698 G - Yet another Number Sequence

【题目链接】​​click here~~​​

【题目大意】

Let's define another number sequence, given by the following function:

f(0) = a

f(1) = b

f(n) = f(n-1) + f(n-2), n > 1

When a = 0 and b = 1, this sequence gives the Fibonacci Sequence. Changing the values ofa and b , you can get many different sequences. Given the values ofa, b, you have to find the last m digits of f(n) .

Input

The first line gives the number of test cases, which is less than 10001. Each test case consists of a single line containing the integersa b n m. The values of a and b range in[0,100], value of n ranges in [0, 1000000000] and value ofm ranges in [1, 4].

Input

The first line gives the number of test cases, which is less than 10001. Each test case consists of a single line containing the integersa b n m. The values of a and b range in[0,100], value of n ranges in [0, 1000000000] and value ofm ranges in [1, 4].

Output

For each test case, print the last m digits of f(n). However, you shouldNOT print any leading zero.

【解题思路】

类似于fibonacci数列的求法，值得注意的是题目并不是让求简单的F（n）,而是求f(n)%f(m),由题目可知，

m ranges in [1, 4].于是定义一个mod数组 const int mod[5]= {0,10,100,1000,10000};每次取模即可

代码

#include #include #include #include #include using namespace std;const int mod[5]= {0,10,100,1000,10000};const int MOD =1e9+7;#define LL long longLL X,Y,N,M,i,j;struct Matrlc{ int mapp[2][2];} ans,base;Matrlc unit= {1,0,0,1};Matrlc mult(Matrlc a,Matrlc b){ Matrlc c; for(int i=0; i<2; i++) for(int j=0; j<2; j++) { c.mapp[i][j]=0; for(int k=0; k<2; k++) c.mapp[i][j]+=(a.mapp[i][k]*b.mapp[k][j])%mod[M]; c.mapp[i][j]%=mod[M]; } return c;}void pow1(int n){ base.mapp[0][0] =base.mapp[0][1]=base.mapp[1][0]=1; base.mapp[1][1]=0; ans.mapp[0][0] = ans.mapp[1][1] = 1;// ans 初始化为单位矩阵 ans.mapp[0][1] = ans.mapp[1][0] = 0; while(n) { if(n&1) ans=mult(ans,base); base=mult(base,base); n>>=1; } // return ans.mapp[0][1];}int main(){ int t; scanf("%d",&t); while(t--) { scanf("%lld%lld%lld%lld",&X,&Y,&N,&M); if(N==0) return X; else if(N==1) return Y; else { pow1(N-1); LL result=(ans.mapp[0][0]*Y+ans.mapp[0][1]*X)%mod[M]; printf("%lld\n",result); } } return 0;}

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