在 O(logn) 中找到第 n 个 fib 数

Question

我正在尝试解决这个问题：SPOJ problem。

经过一些研究，我发现它归结为第 n 个 fib 数的简单计算，但是 n 可能会变得非常大，因此 O(n) 解决方案不会有任何好处。谷歌搜索，我发现你可以计算 O(logn) 中的第 n 个 fib 数，还有一个代码示例可以做到这一点：

long long fibonacci(int n) {
    long long fib[2][2] = {{1,1},{1,0}}, ret[2][2] = {{1,0},{0,1}}, tmp[2][2] = {{0,0},{0,0}};
    int i, j, k;
    while (n) {
        if (n & 1) {
            memset(tmp, 0, sizeof tmp);
            for (i = 0; i < 2; i++)
                for (j = 0; j < 2; j++)
                    for (k = 0; k < 2; k++)
                        tmp[i][j] = (tmp[i][j] + ret[i][k] * fib[k][j]);
            for (i = 0; i < 2; i++)
                for (j = 0; j < 2; j++)
                    ret[i][j] = tmp[i][j];
        }
        memset(tmp, 0, sizeof tmp);
        for (i = 0; i < 2; i++)
            for (j = 0; j < 2; j++)
                for (k = 0; k < 2; k++)
                    tmp[i][j] = (tmp[i][j] + fib[i][k] * fib[k][j]);
        for (i = 0; i < 2; i++)
            for (j = 0; j < 2; j++)
                fib[i][j] = tmp[i][j];
        n /= 2;
    }
    return (ret[0][1]);
}

我尝试修改它以解决问题，但仍然收到 WA：http://ideone.com/3TtE5m

我是不是算错了模运算？还是其他问题？

Answer 1

你的意思是我希望的第n个斐波那契数。

为此，您需要对 here.

中描述的斐波那契数列进行矩阵分解

基本思路是采用 Donald E. Knuth 矩阵恒等式表示斐波那契数，即：

而不是以传统方式计算斐波那契数列，您将尝试找到 (k) 次方的矩阵，其中 k 是给定的数字。

所以这是在解决 k 矩阵乘法的问题，并不是很有帮助，因为我们可以用更简单的方法来做。

但是等等！我们可以优化矩阵乘法。我们可以先对它进行平方，然后再进行一半的乘法，而不是进行 k 次乘法。我们可以继续这样做。因此，如果给定的数字是 2^a 那么我们可以在 a 步中完成。通过保持矩阵的平方。

如果这个数不是2的幂，我们可以对一个数进行二元分解，看是否将给定的平方矩阵作为最终乘积。

在您的情况下，每次乘法后，您还需要对每个矩阵元素应用模运算符 123456。

如果看不到 link 更清晰更长的内容，希望我的解释能有所帮助。

这个任务实际上还有一个警告：当您被要求提供一些斐波那契数对给定数取模时，您还应该证明取每个矩阵元素的余数不会改变结果。换句话说，如果我们乘以矩阵并取余，我们实际上仍然得到斐波那契数的余数。但是由于余数运算在加法和乘法中是分配的，它实际上确实产生了正确的结果。

Answer 2

有一个非常简单的算法，只使用整数：

long long fib(int n) {
    long long a, b, p, q;
    a = q = 1;
    b = p = 0;
    while (n > 0) {
        if (n % 2 == 0) {
            long long qq = q*q;
            q = 2*p*q + qq;
            p = p*p + qq;
            n /= 2;
        } else {
            long long aq = a*q;
            a = b*q + aq + a*p;
            b = b*p + aq;
            n -= 1;
        }
    }
    return b;
}

这是基于identities of the Lucas sequence。

Answer 3

斐波那契数以的连续分数的连续收敛之比出现，由任何连续分数的连续收敛形成的矩阵的行列式为+1或−1.

矩阵表示给出了斐波那契数列的以下封闭形式表达式，即

矩阵乘 n 次，因为只有这样我们才能得到 (n+1)th 斐波那契数作为结果矩阵中 (0, 0) 行和列的元素。

如果我们应用上述方法而不使用递归矩阵乘法，则Time Complexity: O(n)和Space Complexity: O(1)。

但是我们想要Time Complexity: O(log n)，所以我们要优化上面的方法，可以通过矩阵递归乘法得到nth次方

上面规则的实现可以在下面找到。

#include <stdio.h>

void multiply(int F[2][2], int M[2][2]);

void power(int F[2][2], int n);

/*
The function that returns nth Fibonacci number.
*/

int fib(int n) {
    int F[2][2] = {{1, 1}, {1, 0}};
    if (n == 0)
        return 0;
    power(F, n - 1);
    return F[0][0];
}

/*
Optimized using recursive multiplication.
*/

void power(int F[2][2], int n) {
    if ( n == 0 || n == 1)
        return;
    int M[2][2] = {{1, 1}, {1, 0}};
    power(F, n / 2);
    multiply(F, F);
    if (n % 2 != 0)
        multiply(F, M);
}

void multiply(int F[2][2], int M[2][2]) {
    int x = F[0][0] * M[0][0] + F[0][1] * M[1][0];
    int y = F[0][0] * M[0][1] + F[0][1] * M[1][1];
    int z = F[1][0] * M[0][0] + F[1][1] * M[1][0];
    int w = F[1][0] * M[0][1] + F[1][1] * M[1][1];
    F[0][0] = x;
    F[0][1] = y;
    F[1][0] = z;
    F[1][1] = w;
}

int main() {
    printf("%d\n", fib(15));
    /*
    15th Fibonacci number is 610.
    */
    return 0;
}

在 O(logn) 中找到第 n 个 fib 数

Finding the nth fib number, in O(logn)

c

fibonacci