Android学习之——(4)项目中的调用WebService学习
Problem B
Yet another Number Sequence
Input: standard input
Output: standard output
Time Limit: 3 seconds
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 of a and b , you can get many different sequences. Given the values of a, 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 integers a b n m. The values of a and b range in [0,100], value of n ranges in [0, 1000000000] and value of m ranges in [1, 4].
Output
For each test case, print the last m digits of f(n). However, you should NOT print any leading zero.
Sample Input Output for Sample Input
4 0 1 11 3 0 1 42 4 0 1 22 4 0 1 21 4
|
89 4296 7711 946 |
#include <iostream> #include <cstdio> #include <cstring> #include <vector> #include <string> #include <algorithm> #include <queue> using namespace std; int a,b,n,m,mod; struct Mat{ int mat[2][2]; Mat(){ memset(mat,0,sizeof(mat)); } }; Mat operator *(Mat a,Mat b){ Mat c; for(int i = 0; i < 2; i++) for(int j = 0; j < 2; j++) for(int m = 0; m < 2; m++){ c.mat[i][j] = (c.mat[i][j]+a.mat[i][m]*b.mat[m][j])%mod; } return c; } Mat pow_mod(Mat a,int n){ Mat res; for(int i = 0; i < 2; i++) res.mat[i][i] = 1; while(n){ if(n&1) res = res*a; n >>= 1; a = a*a; } return res; } int main(){ int ncase; cin >> ncase; while(ncase--){ cin >> a >> b >> n >> m; if(n==0){ cout<<a<<endl; continue; } mod = 1; while(m--) mod*=10; Mat mm; mm.mat[0][0] = 0;mm.mat[0][1] = 1;mm.mat[1][0] = 1;mm.mat[1][1] = 1; Mat res = pow_mod(mm,n-1); cout<<((res.mat[1][0]*a)%mod+(res.mat[1][1]*b)%mod)%mod<<endl; } return 0; }
郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。