本文主要是介绍【矩阵快速幂】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.
4 0 1 11 3 0 1 42 4 0 1 22 4 0 1 21 4
| 89 4296 7711 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的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
