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

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

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

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