【HDU-4549】M斐波那契数列【数论+矩阵快速幂】

【HDU-4549】M斐波那契数列【数论+矩阵快速幂】

问题链接:https://vjudge.net/problem/HDU-4549

Solution:

首先应该注意到,如果将每一项都使用a、b的幂的积来表示,它们各自的幂次都是斐波那契数列中的项,并且二者只差一项。接着注意到,幂次是斐波那契数列,当然也需要取模,但是不能随便取,当然也不能取1000000007【注意:\(a^b % c \neq (a %c)^{b%c}%c\),一定要注意这一点】,所以使用费马小定理得知幂次应当对1000000006取模。

参考了:https://blog.csdn.net/u013050857/article/details/44999127,感谢博主的分享。

#include <iostream>

using namespace std;

typedef long long LL;
const LL MOD = 1e9 + 7;
const LL EXMOD = 1e9 + 6;
const int LIM = 2;
LL a, b, n;

struct Matrix {
    LL 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] % EXMOD) % EXMOD;
        return ret;
    }
};

Matrix fastPow(LL p, Matrix base) {
    Matrix ret = {1, 0, 0, 0};
    while (p) {
        if (p & 1) ret = base * ret;
        p >>= 1;
        if (p) base = base * base;
    }
    return ret;
}

LL fastPow(LL p, LL base) {
    LL ret = 1;
    while (p) {
        if (p & 1) ret = ret * base % MOD;
        p >>= 1;
        if (p) base = base * base % MOD;
    }
    return ret;
}

int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    const Matrix base = {1, 1, 1, 0};
    while (cin >> a >> b >> n) {
        if (n == 0) cout << a << "\n";
        else if (n == 1) cout << b << "\n";
        else {
            Matrix trans = fastPow(n - 1, base);
            cout << fastPow(trans.v[1][0], a) * fastPow(trans.v[0][0], b) % MOD << "\n";
        }
    }
    return 0;
}