## 【HDU-4686】Arc of Dream【矩阵快速幂】

【HDU-4686】Arc of Dream【矩阵快速幂】

Solution:

$$a_nb_n = AX \times BXa_{n – 1}b_{n – 1} + AX \times BYa_{n – 1} + BX \times AYb_{n – 1} + AY \times BY$$

#include <iostream>

using namespace std;

typedef long long LL;
const LL MOD = 1e9 + 7;
const int LIM = 5;
LL n, a0, ax, ay, b0, bx, by;
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]) % MOD;
return ret;
}
};

LL fastPow(LL p, Matrix base) {
Matrix ret = {0};
ret.v[0][0] = a0 * b0 % MOD;
ret.v[1][0] = a0;
ret.v[2][0] = b0;
ret.v[3][0] = 1;
ret.v[4][0] = a0 * b0 % MOD;
while (p) {
if (p & 1) ret = base * ret;
p >>= 1;
if (p) base = base * base;
}
return ret.v[4][0];
}

int main(void) {
ios::sync_with_stdio(false);
cin.tie(NULL);
while (cin >> n >> a0 >> ax >> ay
>> b0 >> bx >> by) {
if (!n) {
cout << 0 << "\n";
continue;
}
ax %= MOD, bx %= MOD, ay %= MOD, by %=MOD, a0 %= MOD, b0 %= MOD;
Matrix base = {ax * bx % MOD, ax * by % MOD, ay * bx % MOD, ay * by % MOD, 0,
0, ax, 0, ay, 0,
0, 0, bx, by, 0,
0, 0, 0, 1, 0,
ax * bx % MOD, ax * by % MOD, ay * bx % MOD, ay * by % MOD, 1};
cout << fastPow(n - 1, base) << "\n";
}
return 0;
}