UVA - 10689 Yet another Number Sequence 矩阵快速幂

Yet another Number Sequence

Let’s deﬁne 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 diﬀerent sequences. Given the values of a, b, you have to ﬁnd the last m digits of
f(n).
Input
The ﬁrst 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
4
0 1 11 3
0 1 42 4
0 1 22 4
0 1 21 4
Sample Output
89
4296
7711
946

题意：

给你 f[0],f[1] 分别为A,B求F[n] % （10^m）

题解：

n有点大，矩阵快速幂

#include <iostream>

#include <cstdio>

#include <cmath>

#include <cstring>

#include <algorithm>

using namespace std ;

typedef long long ll;

const int  N =  + ;

const int mod = 1e9 + ;

const int M[] = {, , , , };

struct Matrix {

    ll mat[][];

}U,F,L;

ll MOD;

Matrix multi (Matrix a, Matrix b) {

    Matrix ans;

    for(int i = ; i < ; i++) {

        for(int j = ; j < ; j++) {

            ans.mat[i][j] = ;

            for(int k = ; k < ; k++)

                ans.mat[i][j] += a.mat[i][k] * b.mat[k][j];

            ans.mat[i][j] %= MOD;

        }

    }

    return ans;

}

ll a,b,m;

Matrix powss(ll n) {

   Matrix ans = L,p = U;

   while(n) {

    if(n&) ans = multi(p,ans);

    n >>= ;

    p = multi(p,p);

   }

    return ans;

}

int main() {

    int T;

    scanf("%d",&T);

    while(T--) {

            ll n;

        scanf("%lld%lld%lld%lld",&a,&b,&n,&m);

        U = {,,,};

        L = {b,,a,};

        MOD = M[m];

        Matrix ans = powss(n);

        printf("%lld\n",ans.mat[][]);

    }

    return ;

}

巴特西

UVA - 10689 Yet another Number Sequence 矩阵快速幂

最新文章

热门文章