见《数据结构》习题解析 [1-20]

$$\begin{pmatrix} 0&1\\ 1&1\\ \end{pmatrix}^n \times \begin{pmatrix} fib(0)\\ fib(1)\\ \end{pmatrix} = \begin{pmatrix} fib(n)\\ fib(n+1)\\ \end{pmatrix} $$

结合习题解析 [1-14] 的 power2() 算法（快速幂），构造矩阵类，定义矩阵乘法之后，即可完成。

注意初始构造的时候可能单位矩阵和全 0 矩阵即可，然后把加法和乘法的取模也用函数封装一下会更好。

#include <stdio.h>
#include <string.h>
typedef long long i64;

const int mod = 1000000007;
int add(int a, int b) { return (a + b >= mod) ? (a - mod + b) : (a + b); }
int mul(int a, int b) { return 1ll * a * b % mod; }


struct mat
{
    int a[2][2];
    // flag 0 : zero matrix 1 : identity matrix
    mat(bool flag = 0)
    {
        memset(a, 0, sizeof(a));
        for (int i = 0; i < 2; ++i) a[i][i] = flag;
    }
    mat operator*(const mat& o) const
    {
        mat ret; // assert(n == o.n)
        for (int i = 0; i < 2; ++i)
            for (int j = 0; j < 2; ++j)
                for (int k = 0; k < 2; ++k)
                    ret.a[i][j] = add(ret.a[i][j], mul(a[i][k], o.a[k][j]));
        return ret;
    }
    mat operator^(i64 p) const
    {
        mat ret(1);
        mat tmp = (*this);
        while (p)
        {
            if (p & 1) ret = ret * tmp;
            tmp = tmp * tmp, p >>= 1;
        }
        return ret;
    }
    void print() const { printf("%d %d\n%d %d\n", a[0][0], a[0][1], a[1][0], a[1][1]); }
};
int T;
i64 n;
int main()
{
    scanf("%d", &T);
    mat standard, mul;
    standard.a[1][1] = 1;
    mul.a[0][1] = mul.a[1][0] = mul.a[1][1] = 1;
    while (T--)
    {
        scanf("%lld", &n);
        printf("%lld\n", ((mul ^ n) * standard).a[0][1]);
    }
}