斐波纳契数列(矩乘快速幂)

Description

矩阵乘法，构建一个矩阵为

0 1
1 1

由于矩阵具有结合律，所以可以快速幂。每次把n二进制拆分，矩阵自乘

时间O（log n）

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define MOD 123456789
using namespace std;
long long n;
long long a[3][3],b[3],k1,k2,k3,k4;
int main()
{
        scanf("%lld",&n);
        a[1][1]=0;
        a[1][2]=1;
        a[2][1]=1;
        a[2][2]=1;
        b[1]=1;
        b[2]=1;
        n--;
        while(n)
        {
            if(n&1)
            {
                k1=b[1]*a[1][1]+b[2]*a[2][1];
                k2=b[1]*a[1][2]+b[2]*a[2][2];
                b[1]=k1%MOD;
                b[2]=k2%MOD;
            }
            n/=2;
            k1=a[1][1]*a[1][1]+a[1][2]*a[2][1];
            k2=a[1][1]*a[1][2]+a[1][2]*a[2][2];
            k3=a[2][1]*a[1][1]+a[2][2]*a[2][1];
            k4=a[2][1]*a[1][2]+a[2][2]*a[2][2];
            a[1][1]=k1%MOD;
            a[1][2]=k2%MOD;
            a[2][1]=k3%MOD;
            a[2][2]=k4%MOD;
        }
        printf("%lld\n",b[1]);
    return 0;
}