斐波那契数列的Log(n)解法

题目大意

题目中定义了一个新的Super Fibonacci数列.

$$F_{0}=F_{1}=F_{2}=F_{3}=F_{4} = 1$$

$$F_{N}= 2018 \times F_{N-1} + 2017 \times F_{N-2} + 2016 \times F_{N-3} + 2015 \times F_{N-4} + 2014 \times F_{N-5}$$

给定一个N, 我们计算数列的第N个值是多少.

题目中的N是很大的, 有64位int的大小, 每增加一项, 需要5个乘法, 5个加法. 挨个计算是一定会超时的. 但是有什么更简单的方法呢?

普通Fibonacci的计算

读完题目, 我就在想普通Fibonacci数列的计算, 因为之前有了解过Log(n)的计算方法, 是通过矩阵进行快速幂的方式进行.

$$F_{N}= F_{N-1} + F_{N-2}$$

方法大概是这样的:

$$M1 \times M = M2$$

如果我们简单Fibonacci的计算带入到公式里.

$$ $$\begin{bmatrix} F_{N-1} & F_{N-2} \ 0 & 0 \end{bmatrix}$$ \times $$\begin{bmatrix} 1 & 1 \ 1 & 0 \end{bmatrix}$$

$$\begin{bmatrix} F_{N} & F_{N-1} \ 0 & 0 \end{bmatrix}$$ $$

这里的M就是 $$\begin{bmatrix} 1 & 1 \ 1 & 0 \end{bmatrix}$$

而 $$M_{1} \times M \times M … \times M = M_{n}$$ , 就可以转换成下列等式 $M_{1} \times M^{n} = M_{n}$, 只要求解出$M^{n}$, 就能得到计算结果.

这样的方法, 求出M数组就很重要了?

如何求解关键的M数组

这里我提供一种简单的思路. 针对Super Fibonacci. 我们可以这样设置: 首先这个M数组 一定是一个$5 \times 5$的矩阵, 而后, 我们可以假设$M_{n-1}$的第一行是这样的.

$$\begin{bmatrix} F_{n-1} & F_{n-2} & F_{n-3} & F_{n-4} & F_{n-5} \end{bmatrix}$$

那么$M_{n}$的第一行就应该是这样的.

$$\begin{bmatrix} F_{n} & F_{n-1} & F_{n-2} & F_{n-3} & F_{n-4} \end{bmatrix}$$

别问我为什么是这样, 假如不是这样, 你怎么进行迭代. 有了上述假设, 我们把其他行 全部填0.

根据两个数组的第一行, 我想能够推导出来M数组(根据逆推法, 计算一下矩阵的乘法):

$$\begin{bmatrix} 2018 & 1 & 0 & 0 & 0 \ 2017 & 0 & 1 & 0 & 0 \ 2016 & 0 & 0 & 1 & 0 \ 2015 & 0 & 0 & 0 & 1 \ 2014 & 0 & 0 & 0 & 0 \end{bmatrix}$$

对于任意的n, 我们可以先求出$M^{n}$, 就可以获得最终结果.

矩阵快速幂的使用

这是一个简答的快速幂求解方案, 求解$a^{b}$, 下方的 Java代码来自快速幂

private static int cifang(int a, int b) {
    int s = 1;
    while (b > 0) {
        if (b % 2 == 1) { // b=b>>1保证了在最后一步肯定会执行该if判断
            s = s * a;
        }
        a = a * a;
        b = b >> 1;
    }
    return s;
}

对于我们来说, 快速幂是针对矩阵来做的.

unsigned long long orig_m_mtx[][5] = {
    {2018, 1, 0, 0, 0},
    {2017, 0, 1, 0, 0},
    {2016, 0, 0, 1, 0},
    {2015, 0, 0, 0, 1},
    {2014, 0, 0, 0, 0},
}; // M数组

// 快速幂的实现代码, 可对比上方的Java代码
unsigned long long get_rlt(unsigned long long n) {
    if(n < 5) return 1;
    int cur = n - 4;

    unsigned long long m_mtx[5][5];
    unsigned long long m_mtx_tmp[5][5];


    unsigned long long mtx_rlt[5][5] {  // int s = 1;
        {1, 0, 0, 0, 0},
        {0, 1, 0, 0, 0},
        {0, 0, 1, 0, 0},
        {0, 0, 0, 1, 0},
        {0, 0, 0, 0, 1},
    };
    save_mtx(m_mtx, orig_m_mtx);

    while(cur > 0) {
        if(cur % 2 == 1) {
            mk_times(m_mtx, mtx_rlt, m_mtx_tmp); // m_mtx_tmp = m_mtx * mtx_rlt
            save_mtx(mtx_rlt, m_mtx_tmp);        // mtx_rlt = m_mtx_tmp
        }
        mk_twice(m_mtx, m_mtx_tmp);              // m_mtx_tmp = m_mtx * m_mtx
        save_mtx(m_mtx, m_mtx_tmp);              // m_mtx = m_mtx_tmp
        cur  = cur >> 1;
    }

    return mk_rlt(mtx_rlt);
}

详细代码见gist.

扩展方法(O(1))

学过线性代数的话, 可能能够看懂以下的解法 The Linear Algebra View of the Fibonacci Sequence, 这个解法可以直接求出通项. 但是计算量不小, 哈哈.