NC591 题解 | #牛牛的Fib序列#

题意分析

• 题目给出一个序列的前两项，需要我们计算这个序列的第n项的值，并且题目给出序列满足$f[i]=f[i-1]+f[i+1]f[i]=f[i-1]+f[i+1]$

思路分析

• 首先，我们对上面的公式进行推导

• 所以我们可以得到每一项的数值就是这个位置的前1项-前2项。但是我们发现给出的n很大，如果我们直接利用循环求解时间复杂度是很大的。所以我们需要想办法求解。知道菲薄纳西数列第n项求解的同学都知道，这里有一种利用矩阵加速递推的方法可以在对数级别上面求解。所以我们想这个办法进行求解。

解法一 矩阵加速

• 下面我们给出矩阵推导的过程

• 根据推导的结果，我们只需要计算那个矩阵的n次方的结构，然后执行矩阵的运算即可。

• 代码如下

  • 矩阵快速幂的时间复杂度为log级别的，所以时间$O(2^{3}logn)O(2^3logn)$，$2^{3}2^3$是矩阵乘法所消耗的时间，可以看成是$O(logn)O(logn)$
  • 在过程中构造了一个$1x21x2$的矩阵和$2x22x2$的矩阵，空间复杂度很小，可以近似看成是$O(1)O(1)$

class Solution {
public:
    /**
     * 
     * @param a int整型 
     * @param b int整型 
     * @param n int整型 
     * @return int整型
     */
    typedef long long ll;
    const int mod = 1e9+7;
    // 进行两个矩阵之间的乘法
    void mul(int f[2],int a[2][2]){
        int c[2];
        memset(c,0,sizeof(c));
        // 利用线性代数的基本知识
        for(int j=0;j<2;j++){
            for(int k=0;k<2;k++){
                c[j]=(c[j]+(ll)f[k]*a[k][j])%mod;
            }
        }
        // 将新的矩阵赋值给原来的矩阵
        memcpy(f,c,sizeof(c));
    }
    
    // 一个矩阵自己乘上自己
    void mulself(int a[2][2]){
        int c[2][2];
        memset(c,0,sizeof(c));
        // 利用线性代数的基本知识
        for(int i=0;i<2;i++){
            for(int j=0;j<2;j++){
                for(int k=0;k<2;k++){
                    c[i][j]=(c[i][j]+(ll)a[i][k]*a[k][j])%mod;
                }
            }
        }
        // 将新的矩阵赋值给原来的矩阵
        memcpy(a,c,sizeof(c));
    }
    int solve(int a, int b, int n) {
        // write code here
        int f[2]={a,b};
        // 矩阵的初始化
        int x[2][2]={{0,-1},{1,1}};
        n--;
        // 矩阵快速幂操作
        for(;n;n>>=1){
            if(n&1) mul(f,x);
            mulself(x);
        }
        
        return (f[0]%mod+mod)%mod;
    }
};

解法二 矩阵推导找规律

• 但是我发现提交代码之后的效果竟然不是很好，然后我就继续推导看有没有更好更快的方法，首先，我猜测应该有规律，所以我打表进行验证，发现确实有规律，这是一个以6为周期的一个序列，我们只需要求出前6项即可。但是我们就就此止步吗？显然作为一名学习者就应该刨根问底。然后我就利用上面的解法进行了推导验证，验证结果如下

• 代码如下
  • 只需要计算出前6项的值，然后取余数即可，时间复杂度为$O(1)O(1)$
  • 过程中只用了少数几个变量，空间复杂度为$O(1)O(1)$

class Solution {
public:
    /**
     * 
     * @param a int整型 
     * @param b int整型 
     * @param n int整型 
     * @return int整型
     */
    typedef long long ll;
    const int mod=1e9+7;
    ll x[10];
    int solve(int a, int b, int n) {
        // write code here
        // 为了方便我们下标从0开始
        x[0]=a,x[1]=b;
        // 找到一个周期内的每个数值即可
        for(int i=2;i<6;i++){
            x[i]=x[i-1]-x[i-2];
        }
        // 取n是对应的哪个位置
        return (x[(n-1)%6]%mod+mod)%mod;
    }
};