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;
}