P0068 斐波那契II

给定一个整数 n，要求计算斐波那契数列的第 n 项对 $10^9+7$ 取模的结果。

斐波那契序列 $F_1, F_2,...$ 定义为

$$     F_1 = 1, F_2 = 1, F_n = F_{n-2} + F_{n-1} \  \ (n\ge3). $$

注意到斐波那契数列中存在线性关系

$$ \begin{pmatrix} F_n \\ F_{n-1} \end{pmatrix} = \begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix} \begin{pmatrix} F_{n-1} \\ F_{n-2} \end{pmatrix} = \begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix}^{{n-1}} \begin{pmatrix} 1 \\ 1 \end{pmatrix} $$

可以看出若记 $A = \begin{pmatrix}1 & 1 \\ 1 & 0\end{pmatrix}$ 则求 $F_n$ 就转换为对矩阵 $A$ 求幂。

代码

struct M {
    i64 a, b, c, d;
    M(i64 a=1, i64 b=1, i64 c=1, i64 d=0): a(a), b(b), c(c), d(d) {}
};

M m_mul(const M &x, const M &y) {
    return M(
        (x.a * y.a + x.b * y.c) % MOD,
        (x.a * y.b + x.b * y.d) % MOD,
        (x.c * y.a + x.d * y.c) % MOD,
        (x.c * y.b + x.d * y.d) % MOD
    );
}

M m_pow(M base, int n) {
    M res(1, 0, 0, 1);
    while(n) {
        if (n & 1) res = m_mul(res, base);
        base = m_mul(base, base);
        n >>= 1;
    }
    return res;
}

时间复杂度 $\cal O(\log n)$