题解小白月赛20

A题斐波那契
思路因为数据太大，暴力时间复杂度态度，要用矩阵快速幂来降复杂度
代码:

#include<bits/stdc++.h>
using namespace std;
#define ll long long

inline ll read()
{
    ll num=0,w=0;
    char ch=0;
    while(!isdigit(ch))
    {
        w|=ch=='-';
        ch=getchar();
    }
    while(isdigit(ch))
    {
        num=(num<<3)+(num<<1)+(ch^48);
        ch=getchar();
    }
    return w?-num:num;
}

inline void write(int x)
{
    if(x<0)
    {
        putchar('-');
        x=-x;
    }
    if(x>9)
        write(x/10);
    putchar(x%10+'0');
}
const int mod = 1e9+7;
struct mat
{
    ll a[15][15];
    mat(){ //重载
        memset(a,0,sizeof(a));
    }
};
mat mul(mat x,mat y)
{
    mat res;
    for(int i=0;i<2;i++)
        for(int j=0;j<2;j++)
            for(int k=0;k<2;k++)
                res.a[i][j] = (res.a[i][j]+x.a[i][k]*y.a[k][j])%mod;
    return res;
}
ll qpow(int p)
{
    mat bas;//基础矩阵
    mat res;//单位矩阵
    for(int i=0;i<2;i++)
        res.a[i][i] = 1;
    bas.a[0][0] = bas.a[0][1] = bas.a[1][0] = 1;
    bas.a[1][1] = 0;
    while(p)
    {
        if(1&p) res = mul(res,bas);
        bas = mul(bas,bas);
        p>>=1;
    }
    return res.a[0][1];//或者res.a[1][0]
}

int main(){
    ll n =read();
    cout<<qpow(n)*qpow(n+1)<<endl;
}