【矩阵快速幂】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

Output

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

0 1 11 3

0 1 42 4

0 1 22 4

0 1 21 4

946

【解题思路】

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

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

代码

#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
#include <math.h>
using namespace std;
const int mod[5]= {0,10,100,1000,10000};
const int MOD =1e9+7;
#define LL long long
LL 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;
}

这篇关于【矩阵快速幂】UVA 10698 G - Yet another Number Sequence的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！