牛客编程巅峰赛S2第3场 - 青铜&白银&黄金 B 简单的公式

发现，看式子是个递推，所以是矩阵乘法。

和

class Solution {
public:
    typedef long long ll
    ll mod=1e9+7;
    struct nkl{
        ll d[3][3];
    };
    inline ll Get(ll n,ll x,ll y,ll xx,ll yy,ll zz){
        if(n==1) return x;
        if(n==2) return y;
        n-=2;
        nkl a;
        memset(a.d,0,sizeof(a.d));
        a.d[0][0]=xx,a.d[0][1]=yy;a.d[1][0]=zz;
        ll ans[10]={y,x};
        for (;n;n>>=1){
            if(n&1){
                ll op[10];
                memset(op,0,sizeof(op));
                for (int i=0;i<2;i++)
                    for (int j=0;j<2;j++)
                        op[i]=(op[i]+ans[j]*a.d[i][j]%mod)%mod;
                ans[0]=op[0],ans[1]=op[1];
            }
            nkl tmp;
            memset(tmp.d,0,sizeof(tmp.d));
            for (int i=0;i<2;i++)
                for (int j=0;j<2;j++)
                    for (int k=0;k<2;k++)
                        tmp.d[i][j]+=a.d[i][k]*a.d[k][j]%mod,tmp.d[i][j]%=mod;
            for (int i=0;i<2;i++)
                for (int j=0;j<2;j++)
                    a.d[i][j]=tmp.d[i][j];
        }
        return ans[0];
    }
    int Answerforcn(long long n) {
        ll x=Get(n,2,6,2,3,1);
        ll y=Get(n,7,35,3,10,1);
        int ans=(long long)(x*y%mod);
        return ans;
    }
};