C题矩阵快速幂

显然1e18的复杂度O(n)的dp做法是不可取的
那就矩阵快速幂
如果没有了解可以看下B站OTTFF的视频
就是一个模板题，的确就是wlp大佬说的会的就会

/*
a0=0 a1=1
ai=b*ai-1+ c*ai-2
[0 1]^n * [a0] = [an ]
[c b]     [a1] = [an+1]
*/
long long mod=1e9+7;
const int M=2;
class Ma
{
public:
    long long a[M][M];
    Ma()
    {
        memset(a,0,sizeof(a));
    }
    void become_unit_matrix()
    {
        //设置成单位矩阵
        for (int i=0;i<M;++i)
            for (int j=0;j<M;++j)
                a[i][j]= i==j ? 1 : 0;
    }
    void show()
    {
        cout << "----" << endl;
        cout << "Matrix is " << M << '*' << M << endl;
        for (int i=0;i<M;++i)
        {
            for (int j=0;j<M;++j)
                cout << a[i][j] << ' ';
            cout << endl;
        }
        cout << "----" << endl;
    }
    Ma operator*(const Ma &B) const
    {
        //重载两个矩阵相乘
        Ma ans;
        for (int i=0;i<M;++i)
            for (int j=0;j<M;++j)
                for (int k=0;k<M;++k)
                {
                    ans.a[i][j]+=(((this->a[i][k])%mod)*((B.a[k][j])%mod))%mod;
                    ans.a[i][j]%=mod;
                }
        return ans;
    }
    Ma operator^(long long n) const
    {
        //重载幂次运算，并结合快速幂
        Ma ans;
        //单位矩阵乘任何矩阵还是任何矩阵本身
        ans.become_unit_matrix();
        Ma A=*this;
        while(n!=0)
        {
            if ((n&1)==1)
                ans=ans*A;
            A=A*A;
            n>>=1;
        }
        return ans;
    }
};
class Solution {
public:
    long long nthElement(long long n, long long b, long long c) {
        Ma A;
        A.a[0][0]=0;
        A.a[0][1]=1;
        A.a[1][0]=c;
        A.a[1][1]=b;
        Ma F;
        F.a[0][0]=0;
        F.a[1][0]=1;
        Ma ans=(A^n)*F;
        return ans.a[0][0];
    }
};