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

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

UVa10689 - Yet another Number Sequence,布布扣,bubuko.com

UVa10689 - Yet another Number Sequence

原文：http://blog.csdn.net/mowayao/article/details/21566531