跳转至

斐波那契

公式

\[ \begin{align} F_0=0,F_1=1\\ F_N=F_{n-1}+F_{n-2} \end{align} \]
\[ F_n=\left[\frac{\dfrac{(1+\sqrt5)^n}{2}-\dfrac{(1-\sqrt5)^n}{2}}{\sqrt5}\right] \]
\[ S_n=F_{n+2}-1 \]
模版

\(O(\log(n))\)

C++
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
using i64 = long long;
const i64 P = 998244353;
pair<i64, i64> fib(i64 n) {
    if (n == 0) {
        return {0, 1};
    }
    auto [a, b] = fib(n / 2);
    i64 c = a * (2 * b - a + P) % P, d = (a * a + b * b) % P;
    if (n & 1) {
        return {d, (c + d) % P};
    }
    return {c, d};
}

P4000 斐波那契数列 - 洛谷

\(O(\sqrt P)\)

随机算法，有错误的可能。

C++
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
using i64 = long long;
using u64 = unsigned long long;
i64 P;
namespace Fibonacci {
    struct Mat {
        i64 a[2][2];
        Mat(bool flag = true) {
            a[0][0] = a[0][1] = a[1][0] = a[1][1] = 0;
            if (flag == true) {
                a[0][0] = a[1][1] = 1;
            }
        }
        i64* operator[](int x) {
            return a[x];
        }
        friend Mat operator*(Mat x, Mat y) {
            Mat res(false);
            for (int i = 0 ; i < 2 ; i++) {
                for (int k = 0 ; k < 2 ; k++) {
                    i64 r = x[i][k];
                    for (int j = 0 ; j < 2 ; j++) {
                        res[i][j] += r * y[k][j];
                    }
                }
            }
            for (int i = 0 ; i < 2 ; i++) {
                for (int j = 0 ; j < 2 ; j++) {
                    res[i][j] %= P;
                }
            }
            return res;
        }
    };
    const int M = 20;
    const int N = (1 << M) - 1;
    array<Mat, 2> mat[N + 1];
    i64 len = 0;
    void init() {
        mt19937_64 rnd(time(nullptr));
        Mat base(false);
        base[0][0] = 0;
        base[0][1] = base[1][0] = base[1][1] = 1;
        for (int i = 1 ; i <= N ; i++) {
            mat[i][0] = mat[i - 1][0] * base;
        }
        Mat base2 = mat[N][0] * base;
        for (int i = 1 ; i <= N ; i++) {
            mat[i][1] = mat[i - 1][1] * base2;
        }
        map<u64, i64> loop;
        while (true) {
            i64 a = rnd() << 28 >> 28;
            Mat res = mat[a & N][0] * mat[a >> M][1];
            u64 val = ((u64) res[0][0] << 32) | res[0][1];
            if (loop.find(val) != end(loop)) {
                len = llabs(loop[val] - a);
                break;
            }
            loop[val] = a;
        }

    }
    i64 get(const string &str) {
        assert(len != 0);
        i64 n = 0;
        for (auto &ch : str) {
            n = (n * 10 + ch - 48) % len;
        }
        return (mat[n & N][0] * mat[n >> M][1])[0][1];
    }
} // Fibonacci

卢卡斯

\[ L_n=(\dfrac{1+\sqrt5}{2})^n+(\dfrac{1-\sqrt5}{2})^n \]
\[ L_n^2-5F_n^2=-4 \]