[TIOJ] 2053 . 費氏數列（Fibonacci）

題目連結：
2053 . 費氏數列（Fibonacci）


題意：
輸入一行五個整數 $x_1, \ x_2, \ a, \ b, \ n$，
求數列 $x_n \ = \ bx_{n-1} \ + \ ax_{n-2}$ 的第 $n$ 項。



解題策略：

• 快速冪
$a^b=\begin{cases}1\;,\;b=0\\(a^{\frac{b}{2}})^2\;,\;\text{b is even}\\(a^{\frac{b}{2}})^2\times a\;,\;\text{b is odd}\end{cases}$
又因 $(a \times b) \ \% \ m \ = \ ((a \ \% \ m) \ \times \ (b \ \% \ m)) \ \% \ m$，
搭配快速冪可在 $O(log \ n)$ 的時間複雜度下得到 $a^b \ \% \ m$。
遞迴版：

long long powi(long long a, long long b, long long m) {
    if (!a && !b)
        return 1;
    if (b == 1)
        return a % m;
    long long tmp = powi(a, b >> 1, m);
    if (b & 1)
        return ((tmp % m) * (tmp % m) * (a % m)) % m;
    else
        return ((tmp % m) * (tmp % m)) % m;
}

迭代版：

long long powi(long long a, long long b, long long m) {
    long long res = 1;
    for (a = (a > m ? a % m : a); b; b >>= 1, a = a * a % m)
        if (b & 1)
            res = res * a % m;
    return res;
}

• 矩陣乘法
$ \left[ \begin{matrix} a & b \\ c & d \\ \end{matrix} \right] \times \left[ \begin{matrix} e & f \\ g & h \\ \end{matrix} \right] \ = \ \left[ \begin{matrix} ae+bg & af+bh \\ ce+dg & cf+dh \\ \end{matrix} \right] $
藉由此概念可以推到以下結果
$ \left[ \begin{matrix} x_n & x_{n+1} \end{matrix} \right] \times \left[ \begin{matrix} 0 & a \\ 1 & b \\ \end{matrix} \right] \ = \ \left[ \begin{matrix} x_{n+1} & ax_n+bx_{n+1} \\ \end{matrix} \right] $
• 矩陣快速冪
以快速冪求矩陣的 $n$ 次方運算， 
所求 = $ \left[ \begin{matrix} x_1 & x_2 \end{matrix} \right] \times {\left[ \begin{matrix} 0 & a \\ 1 & b \\ \end{matrix} \right]}^n $ 的 $M_{11}$。
總時間複雜度為：$O(k^3 \ log \ n)$。

程式碼參考：
$C++$：
$JUDGE\_RESULT$：$100(score), \ 0(ms), \ 3492(KiB)$

#include <iostream>
#include <vector>
#define ll long long
using namespace std;
constexpr ll mod = 1e9 + 7;

class matrix {
#define f first
#define s second
private:
    vector<vector<ll>> d; // data
public:
    inline pair<size_t, size_t> size() { // 回傳矩陣的大小
        return {d.size(), d.front().size()};
    }
    vector<ll>& operator[](size_t i) {
        return d[i];
    }
    inline friend matrix operator*(matrix& a, matrix& b) { // 矩陣乘法
        size_t n = a.size().f, m = a.size().s, r = b.size().s;
        matrix tmp(n, r);
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) { // cur = matrix[i][j]
                for (int k = 0; k < r; k++) {
                    tmp[i][j] += a[i][k] * b[k][j];
                    if (tmp[i][j] > mod)
                        tmp[i][j] %= mod;
                }
            }
        }
        return tmp;
    }
    inline matrix operator*=(matrix& b) {
        return (*this) = (*this) * b;
    }
    matrix(const vector<vector<ll>> v) {
        d = v;
    }
    matrix(const size_t n = 0, const size_t m = 0) {
        d = vector<vector<ll>>(n, vector<ll>(m));
    }
#undef f
#undef s
};

int x1, x2, a, b, n;
matrix powi(int n) { // 矩陣快速冪
    matrix res({{x1, x2}}), tmp({{0, a}, {1, b}});
    for (; n; n >>= 1, tmp *= tmp) {
        if (n & 1)
            res *= tmp;
    }
    return res;
}

#define _ ios::sync_with_stdio(false), cin.tie(nullptr);
int main() { _
    cin >> x1 >> x2 >> a >> b >> n;
    cout << powi(n - 1)[0][0] << '\n';
}

以上，
若有更好的想法歡迎提出哦！