【UVA – 10689】Yet another Number Sequence

【UVA – 10689】Yet another Number Sequence

问题链接:https://vjudge.net/problem/UVA-10689

Solution:

em…不用多想,就是个用矩阵快速幂求第n项。

唯一需要注意的是Output那里有说取模的事情。

#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>

using namespace std;

int MOD = 0;
const int LIM = 2;
struct Matrix {
    int v[LIM][LIM];
    Matrix operator * (const Matrix & m) const {
        Matrix ret = {0};
        for (int i = 0; i < LIM; i++) {
            for (int k = 0; k < LIM; k++) {
                if (v[i][k])
                    for (int j = 0; j < LIM; j++) {
                        ret.v[i][j] = (ret.v[i][j] + v[i][k] * m.v[k][j]) % MOD;
                    }
            }
        }
        return ret;
    }
};

const Matrix BASE = {1, 1, 1, 0};

Matrix fastPow(int p, Matrix m) {
    Matrix ret = {0};
    for(int i = 0; i < LIM; i++) ret.v[i][i] = 1;
    while (p) {
        if (p & 1) ret = ret * m;
        if (p) m = m * m;
        p >>= 1;
    }
    return ret;
}

int main() {
    int t;
    scanf("%d",&t);
    int a, b, n, m;
    while (t--) {
        scanf("%d%d%d%d", &a, &b, &n, &m);
        MOD = 1;
        while (m--) MOD *= 10;
        if (n == 0) printf("%d\n", a);
        else if (n == 1) printf("%d\n", b);
        else {
            Matrix trans = fastPow(n - 1, BASE);
            printf("%d\n", (b * trans.v[0][0] + a * trans.v[0][1]) % MOD);
        }
    }
    return 0;
}