マトリックス演算+高速べき乗でフィボナッチ数列問題を処理する

フィボナッチ数列の問題を定義します.
a 0=1 a 0=1,a 1=1 a 1=1,an=an−1+an−2 an=an−1+an−2を定義し,ananがいくらであるかを求める.整数オーバーフローの問題を考慮しないために,an%pan%pの値,p=109+7 p=109+7を求めた.
高速べき乗アルゴリズムのテンプレートは、ここを参照してください.行列演算の性質を用いて通項式をべき乗次形式に変換し,次いで二乗倍増(高速べき乗)法を用いてnn項を解くことができる.
まず,ベクトルXn=[an−1],境界:X 1=[a 1 a 0]Xn=[an−1],境界:X 1=[a 1 a 0]を定義し,行列:A=[1101]A=[1101]はXn=Xn−1である.×A Xn=Xn−1×Aだから:
Xn=X1×An−1 Xn=X1×An−1は行列に結合則があるので,まずAn−1%PAn−1%Pを求め,その後X 1 X 1で左乗することでXnXnを求めることができ,ベクトルXnXnの最初の要素はananである.
時間複雑度解析:高速べき乗の時間複雑度はO(logn)O(logn)であるため,アルゴリズム5の時間複雑度もO(logn)O(logn)である.
C++コード

#include 
#include 
#include 
#include 
#include 

using namespace std;

const int MOD = 1000000007;

void mul(int a[][2], int b[][2], int c[][2])
{
     
    int temp[][2] = {
     {
     0, 0}, {
     0, 0}};
    for (int i = 0; i < 2; i ++ )
        for (int j = 0; j < 2; j ++ )
            for (int k = 0; k < 2; k ++ )
            {
     
                long long x = temp[i][j] + (long long)a[i][k] * b[k][j];
                temp[i][j] = x % MOD;
            }
    for (int i = 0; i < 2; i ++ )
        for (int j = 0; j < 2; j ++ )
            c[i][j] = temp[i][j];
}


int result(long long n)
{
     
    int x[2] = {
     1, 1};

    int a[2][2] = {
     {
     1, 1}, {
     1, 0}};

    int res[][2] = {
     {
     1, 0}, {
     0, 1}};
    int t[][2] = {
     {
     1, 1}, {
     1, 0}};
    long long k = n - 1;
    while (k)
    {
     
        if (k&1) mul(res, t, res);
        mul(t, t, t);
        k >>= 1;
    }

    int c[2] = {
     0, 0};
    for (int i = 0; i < 2; i ++ )
        for (int j = 0; j < 2; j ++ )
        {
     
            long long r = c[i] + (long long)x[j] * res[j][i];
            c[i] = r % MOD;
        }

    return c[0];
}


int main()
{
     
    long long n ;

    cin >> n;
    cout << result(n) << endl;

    return 0;
}