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

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

Solution:

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