题意：

给你一个数列 ，其中 ， ，
求 的值。

解法一（暴力递推，不可AC）：

根据 可得出 ，因此我们直接循环递推过去即可。

这边我们采用滚动数组的形式，由于每一个只依赖连续的两个值求解，故我们开一个长度为的数组，接下来我们来模拟『填写』值的过程

为了方便，我们将映射到，如表示原来的，表示原来的

：

：

：

：

class Solution {
public:
    const int mod=1e9+7;
    int f[2];//采用滚动数组
    int solve(int a, int b, int n) {
        f[0]=a;
        f[1]=b;
        for(int i=2;i<n;i++){
            f[i%2]=(f[(i-1)%2]-f[(i-2)%2]+mod)%mod;
        }
        return f[(n+1)%2];//这边我们把f[1~n]对应到f[0~n-1]，故我们是求f[n-1],采用滚动数组即f[(n-1+2)%2]=f[(n+1)%2]
    }
};

时间复杂度： ，我们需要一次循环依次递推过去，故时间复杂度为
空间复杂度： ，我们需要开一个长度为2的滚动数组，故空间复杂度为

解法二（正解，矩阵快速幂）：

由 ，我们可以构造如下矩阵乘法式子：

const int mod=1e9+7;
class Solution {
public:
    struct mat{
        int A[2][2];
        inline mat operator * (const mat& other)const{//矩阵乘法
            mat ret;
            memset(ret.A,0,sizeof ret.A);
            for(int i=0;i<2;i++){
                for(int j=0;j<2;j++){
                    for(int k=0;k<2;k++){
                        ret.A[i][j]+=1ll*A[i][k]*other.A[k][j]%mod;//注意爆int
                        ret.A[i][j]%=mod;//A[i][j]=(A[i][j]+X)%mod
                    }
                }
            }
            return ret;
        }
    };
    mat ksm(mat a,int b){//矩阵快速幂
        mat ret;
        memset(ret.A,0,sizeof ret.A);
        for(int i=0;i<2;i++)ret.A[i][i]=1;//单位矩阵
        while(b){
            if(b&1){
                ret=ret*a;
            }
            a=a*a;
            b>>=1;
        }
        return ret;
    }
    int solve(int a, int b, int n) {
        if(n==1)return a;
        if(n==2)return b;//特殊判断
        a=(a+mod)%mod;//把负数弄成正数
        b=(b+mod)%mod;
        mat r;
        r.A[0][0]=1,r.A[0][1]=(-1+mod)%mod;//取模意义下弄成正数
        r.A[1][0]=1,r.A[1][1]=0;
        r=ksm(r,n-2);
        int ans=(1ll*r.A[0][0]*b%mod+1ll*r.A[0][1]*a%mod)%mod;//A[0][0]*f(2)+A[0][1]*f(1)
        //模拟矩阵乘法求出f[n]
        return ans;
    }
};

时间复杂度： ，矩阵的大小为，故矩阵乘法的时间复杂度可视为常数，矩阵快速幂需要进行 次乘法运算，故时间复杂度为
空间复杂度： ，仅需保存 级别内存的矩阵即可。