Yet another Number Sequence 矩阵快速幂

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

0 1 11 3

0 1 42 4

0 1 22 4

0 1 21 4

Sample Output

4296

7711

946

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
#include<cmath>
#include<map>
#include<stack>
#include<set>
#include<string>
using namespace std;
typedef long long  LL;
typedef unsigned long long ULL;
#define MAXN 51
#define MOD 10000007
#define INF 1000000009
const double eps = 1e-9;
//矩阵快速幂
int a, b, n, m, mod;
struct Mat
{
    int a[2][2];
    Mat()
    {
        memset(a, 0, sizeof(a));
    }
    Mat operator*(const Mat& rhs)
    {
        Mat ret;
        for (int i = 0; i < 2; i++)
        {
            for (int j = 0; j < 2; j++)
            {
                for (int k = 0; k < 2; k++)
                    ret.a[i][j] = (ret.a[i][j] + a[i][k] * rhs.a[k][j]) % mod;
            }
        }
        return ret;
    }
};
Mat fpow(Mat m, int b)
{
    Mat ans;
    for (int i = 0; i < 2; i++)
        ans.a[i][i] = 1;
    while (b != 0)
    {
        if (b & 1)
            ans = m * ans;
        m = m * m;
        b = b / 2;
    }
    return ans;
}
Mat M;
int main()
{
    int T;
    scanf("%d", &T);
    while (T--)
    {
        scanf("%d%d%d%d", &a, &b, &n, &m);
        mod = pow(10, m);
        M.a[0][0] = M.a[0][1] = M.a[1][0] = 1;
        M.a[1][1] = 0;
        M = fpow(M, n - 1);
        printf("%d
", (M.a[0][0] * b + M.a[0][1] * a) % mod);
    }
}

Yet another Number Sequence 矩阵快速幂

相关推荐