SDNU1062 Fibonacci（矩阵快速幂模版）

这道题qaq(node x,n)就是求x^n，这是一道模版题。
其中第一个矩阵，另一个是一个数

讲的很好的博客：https://blog.csdn.net/qq_41658955/article/details/87289934

/*少说话，多做事*/
#include <cstdio>
#include <cstring>
#include <string>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <vector>
#include <stack>
#include <sstream>
#include <map>
#include <set>
#include <queue>
#include <stdlib.h>
//#include<bits/stdc++.h>
typedef long long ll;

using namespace std;
const int maxn = 2;
const ll mod=1e9+7;

struct node
{
    ll m[maxn][maxn];
}unit;

void init() //初始化 ,将unit设为单位数组
{
    for(int i=0;i<maxn;i++)
    {
        for (int j=0;j<maxn;j++)
        {
            if(i==j) unit.m[i][j]=1;
            else unit.m[i][j]=0;
        }
    }
}

node matmul(node a,node b)  //定义矩阵的乘法  -> 矩阵乘以矩阵，返回的是矩阵
{
    node ans;
    ll tmp =0;
    for(int i=0;i<maxn;i++)
    {
        for(int j=0;j<maxn;j++)
        {
            tmp=0;
            for(int k=0;k<maxn;k++)
            {
                tmp=(tmp + a.m[i][k] * b.m[k][j])%mod;
            }
            ans.m[i][j]=tmp;
        }
    }
    return ans;
}

ll qaq (node x , ll n) //计算数组^b， --》比如设A为数组，B为一个数，则qaq求的是A^B
{
    init();  //将unit初始化为单位矩阵 ,一开始都是从单位矩阵开始乘的。 -》 就一直按照unit变化，最后得出的答案就是从unit中找，这道题是m[1][0]为fn
    while(n!=0)
    {
        if(n%2==1) //如果b是奇数
        {
            unit = matmul(unit, x); //ans是矩阵，unit也是矩阵
        }
        x = matmul(x, x);
        n>>=1;
    }
    return unit.m[1][0];
}
int main()
{
    ll n;
    while(cin >> n)
    {
        node x = {1,1,1,0};
        cout << qaq(x, n) << endl;
    }
    return 0;
}