Fibonacci数列快速算法

通过fibonacci数列的递推公式，可以将求数列转换为求递推矩阵的n次幂。

\begin{equation}
{\left[ \begin{array}{cc}
0 & 1 \\
1 & 1
\end{array}
\right ]}
\times
{\left[\begin{array}{c}
f_{n} \\
f_{n+1}
\end{array}
\right]}
=
{\left[\begin{array}{c}
f_{n+1} \\
f_{n+2}
\end{array}
\right]}
\end{equation}

题目

#define MODULO (1000000000 + 7)

struct Matrix {
    Matrix() {}
    Matrix(int a00, int a01, int a10, int a11) {
        v[0][0] = a00;
        v[0][1] = a01;
        v[1][0] = a10;
        v[1][1] = a11;
    }
    long v[2][2];
    void multiply(Matrix &other) {
        Matrix res;
        res.v[0][0] = (v[0][0] * other.v[0][0] + v[0][1] * other.v[1][0]) % MODULO;
        res.v[0][1] = (v[0][0] * other.v[0][1] + v[0][1] * other.v[1][1]) % MODULO;
        res.v[1][0] = (v[1][0] * other.v[0][0] + v[1][1] * other.v[1][0]) % MODULO;
        res.v[1][1] = (v[1][0] * other.v[0][1] + v[1][1] * other.v[1][1]) % MODULO;
        *this = res;
    }
};

/*
 * Complete the 'solve' function below.
 *
 * The function is expected to return an INTEGER.
 * The function accepts following parameters:
 *  1. INTEGER a
 *  2. INTEGER b
 *  3. INTEGER n
 */

int solve(int a, int b, int n) {
    Matrix I(0, 1, 1, 1);
    Matrix res(1, 0, 0, 1);
    while (n) {
        if (n & 1) {
            res.multiply(I);
        }
        n >>= 1;
        I.multiply(I);
    }
    return (res.v[0][0] * a % MODULO + res.v[0][1] * b % MODULO) % MODULO;
}