第 30 个斐波那契数

运行下面这段程序：

综合：把逆元、组合数、CRT、矩阵快速幂按题目组合起来用。

#include <array>
#include <iostream>
#include <string>
#include <vector>
using namespace std;

typedef array<array<long long, 2>, 2> Mat;

Mat mat_mul(const Mat& A, const Mat& B, long long p) {
    // 2×2 矩阵乘法，模 p
    Mat C{};
    for (int i = 0; i < 2; i++)
        for (int j = 0; j < 2; j++)
            for (int k = 0; k < 2; k++)
                C[i][j] = (C[i][j] + A[i][k] * B[k][j]) % p;
    return C;
}

long long fib(long long n, long long p) {
    // 矩阵快速幂求第 n 个斐波那契数 mod p（fib(1) = fib(2) = 1）
    Mat R = {{{1, 0}, {0, 1}}};
    Mat A = {{{1, 1}, {1, 0}}};
    while (n > 0) {
        if (n & 1) R = mat_mul(R, A, p);
        A = mat_mul(A, A, p);
        n >>= 1;
    }
    return R[0][1];
}

int main() {
    cout << fib(30, 1000000007) << endl;
}

（本题用 g++ -std=c++17 -O0 编译。）