SDNU 1085 爬楼梯再加强版（矩阵快速幂）

/*少说话，多做事*/
#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>
//ios::sync_with_stdio(0);
//cin.tie(0);
//cout.tie(0);
typedef long long ll;

using namespace std;

/*

 */

const int maxn = 3;
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;
}

node 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;
}

int main()
{
    ll n;
    while(cin >> n)
    {
        if(n==1) cout << "1" << endl;
        else if(n==2) cout << "2" << endl;
        else if(n==3) cout << "4" << endl;
        else
        {
            node x = {1,1,1,1,0,0,0,1,0};
            x = qaq(x, n-3);
            cout << (x.m[0][0]*4%mod + x.m[0][1]*2%mod + x.m[0][2]*1%mod)%mod << endl;
        }
    }
    return 0;
}