Dãy số Fibonacci, tỉ lệ vàng, những cụm từ này đã không còn xa lạ trong giới Toán học, Kinh tế, Nghệ thuật hay Lập trình.

Dãy Fibonacci là dãy vô hạn các số tự nhiên bắt đầu bằng hai phần tử 0 hoặc 1 và 1, các phần tử sau đó được thiết lập theo quy tắc mỗi phần tử luôn bằng tổng hai phần tử trước nó:

Chắc hẳn mọi người ai cũng đã nghe qua bài toán đàn thỏ gắn liền với dãy số này, và sự xuất hiện của tỉ lệ vàng φ ≈ 1.618, con số mà xuất hiện hầu như trong khắp mọi nơi trong tự nhiên.

Khi nói về dãy số này, có vô vàn điều thú vị và hay ho để khám phá về nó, nhưng những chủ đề đó có lẽ sẽ phải hẹn vào dịp khác.

Hôm nay, có một cậu học sinh, hoặc là cậu sinh viên, hay chỉ đơn thuần là một cậu trai, hãy tạm thời gọi cậu là B. B là một người tò mò, hoặc không, cậu luôn luôn lạc quan, hoặc ảm đạm, và cả quyết, hoặc không thể chắc chắn về điều gì. B là ai, chúng ta không thể chắc chắn được nhưng điều đó thật ra không quan trọng vì cho dù B là ai thì chắc chắn rằng ít người đọc và quan tâm đến. Dù vậy có một điều rất rõ, B rất dở tính toán.
B đang tìm tòi học hỏi về dãy số Fibonacci và cậu muốn biết số Fibonacci thứ n sau khi chia lấy dư cho 1000000007. Một bài toán đơn giản. Nhưng vì não cậu không có nhiều nếp nhăn nên cho dù cậu có cố gắng tính toán thế nào cũng bị sai sót.

Bạn, là một lập trình viên và bạn biết C++, hùng hồn đến trước mặt B và tuyên bố:

#include <iostream>
using namespace std;

const int MOD = 1e9 + 7;

int main() {
    int n = 1000000;
    long long a = 0, b = 1;
    for (int i = 2; i <= n; i++) {
        long long c = (a + b) % MOD;
        a = b;
        b = c;
    }
    cout << "F(" << n << ") mod " << MOD << " = " << b << endl;
    return 0;
}

F(1000000) mod 1000000007 = 918091266

Splendid! Bạn lôi ra một đoạn code kinh điển mà bất cứ người học sinh, sinh viên nào học về thuật toán Quy hoạch động đều biết đến. Một vòng lặp duy nhất để tính dần dần số Fibonacci từ 1 đến n bằng chính công thức định nghĩa nên dãy số: F(n) = F(n - 1) + F(n - 2). Với độ phức tạp về thời gian là O(n), nó có thể tính toán chính xác số Fibonacci thứ 1000000 mà chưa cần tới 1 giây.

Bạn tuyên bố đoạn code này trước mặt B, cảm thấy mình như một đấng cứu thế giúp đỡ B, một người đang gặp khó khăn trong cuộc sống trong việc tính toán số Fibonacci, và kì vọng rằng B nhìn bạn với những đôi mắt lấp lánh và biết ơn bạn với cả trái tim.

Và cứ như vậy, B đáp lại:

Ah, bạn giỏi á, 2 năm trước mình cũng từng code một đoạn như vậy và tính ra được số Fibonacci thứ 1000000. Mình cảm ơn tấm lòng của bạn nhưng số Fibonacci mình đang tìm là số Fibonacci thứ 1000000000000000000 kia.

...

Có lẽ bạn đã quên mất rằng chính mình đã nói rằng đó là "đoạn code kinh điển mà bất cứ người học sinh, sinh viên nào học về thuật toán Quy hoạch động đều biết đến". B cũng là một người học ở chung trường, chung ngành và chung lớp với bạn, đó là lí do tại sao bạn lại thấy B đang gặp khó khăn và chạy tới giúp đỡ ngay từ ban đầu. Và đương nhiên, B phải biết tới đoạn code này, và đương nhiên, ai ở trong lớp này cũng biết.

Bạn đứng ở đó, cảm thấy mọi ánh mắt đều hướng nhìn về bạn. Thời gian như đang ngưng đọng lại, đây là khoảnh khắc căng thẳng nhất trong cuộc đời của bạn. Trong 21 nano giây nữa, mọi người trong lớp sẽ nhận thức ra được bộ dạng ra vẻ "đấng cứu thế" của bạn. Sau khi 21 nano giây kết thúc, hoặc là bạn sẽ trở thành một cây hài cho cả lớp và cảm thấy nhục nhã suốt phần đời còn lại của bạn, hoặc là bạn thật sự trở thành một đấng cứu thế và dùng một đoạn code mà không phải học sinh, sinh viên nào đều biết tới khi học Quy hoạch động.

Nhưng bạn biết rõ, bạn không hề biết tới đoạn code đó. Bạn là con mèo Schrödinger nhưng chỉ với một khả năng duy nhất khi chiếc hộp đen được mở ra sau 21 nano giây. Con mèo đã chết. Bạn biết rõ rằng mình cần phải làm gì trong hoàn cảnh này. Trong 21 nano giây, bạn phải tạo ra được khả năng con mèo còn sống.

Với những tế bào não bạn đã dành dụm từ khi được sinh ra, bạn bắt đầu nghĩ.

21 nano giây

Chỉ với độ phức tạp thời gian O(1)...

Trong lớp Kinh tế, bạn đã được học một công thức có liên quan tới tỉ lệ vàng để tính xấp xỉ số Fibonacci.

Là công thức Binet. Chính là nó.

Chỉ cần ráp công thức vào là ra mà không cần phải làm gì nhiều. Độ phức tạp thời gian là O(1) thì muốn tính số Fibonacci số bao nhiêu mà chẳng được?

Đó là những gì bạn đã suy nghĩ. Nhưng rồi bạn nhận ra: bạn phải tính số Fibonacci thứ n sau khi chia lấy phần dư cho 1000000007.

Nếu như nhìn vào công thức, để tính toán được phải áp dụng modulo và nghịch đảo modulo. Và nó không hề dễ chịu một chút nào.

Còn nếu cứ tính thẳng bằng số thực rồi làm tròn, sai số dấu phẩy động sẽ lặng lẽ tích tụ, khi n lớn, con số cuối cùng lệch hoàn toàn so với đáp án đúng.

Bạn phải tìm một cách khác.

17 nano giây

Ma trận. Ma trận á?

Bạn đang suy nghĩ tới ma trận. Không phải là ma trận trong bộ phim mà có một gã đàn ông mặc bộ vest màu đen đột nhiên giơ tay lên, một cách thần kì nào đó chặn hàng loạt viên đạn đang bay tới, mà bạn đang nghĩ tới ma trận trong môn Đại số tuyến tính. Không phải là một ma trận ngẫu nhiên nào, bạn đang nghĩ tới một ma trận đột nhiên xuất hiện trong đầu bạn bằng một cách thần kì nào đó:

Tại sao lại là ma trận này? Bạn thật sự không biết tại sao mình lại nghĩ tới một ma trận ngẫu nhiên này, khi bạn có thể dành thời gian để áp dụng các thuật toán mà các chuyên gia sử dụng thì bạn lại suy nghĩ ra một ma trận hoàn toàn ngẫu nhiên và cụ thể này mà không có tác dụng gì cả? Thật là phí thời gian...

15 nano giây

Bạn đã phí thời gian.

Bạn không kịp suy nghĩ gì. Nhưng với ma trận bạn đã nghĩ ra, bạn quyết định dùng nó để nhân với một vector.

...và lại tiếp tục nhân nó với ma trận đó.

...và bạn cứ tiếp tục.

Bạn nhận ra một thứ gì đó khá quen thuộc. Đúng hơn, các con số, và dãy các con số, bạn cảm thấy chúng rất quen thuộc. Đúng rồi, nó là dãy số Fibonacci!

10 nano giây

Bạn tiếp tục suy nghĩ, bạn suy nghĩ ở mức tổng quát hơn. Bạn đang tưởng tượng việc nhân một vector, có 2 phần tử, phần tử đầu tiên là số Fibonacci thứ n - 1 và phần tử thứ 2 là số Fibonacci thứ n. Bạn thử nhân vector này với ma trận đó.

Bạn nhận ra ngay, nếu tiếp tục...

Nói cách khác, nếu bạn làm thế này:

Thì bạn sẽ tính được số Fibonacci thứ n!

6 nano seconds

Bạn cần một thuật toán để tính được lũy thừa bậc n - 1 của ma trận trên với độ phức tạp thời gian thấp. Ít nhất là phải thấp hơn O(n), nếu không công sức trong 15 nano giây lúc nãy trở thành công cốc. Một thuật toán với độ phức tạp về thời gian O(logn) thì sao? Thuật toán có độ phức tạp O(logn)? Segment Tree? tìm kiếm nhị phân? Chia để trị?...

4 nano giây

Chia để trị!

Bạn để ý tới một điều:

Để tính lũy thừa ma trận bậc k, bạn cần tính lũy thừa ma trận bậc k/2. Để tính lũy thừa ma trận bậc k/2, bạn cần tính lũy thừa ma trận bậc k/4...

1 nano giây

Với kĩ năng anh hùng bàn phím của bạn...

#include <iostream>
#include <assert.h>
#include <vector>
using namespace std;

#define LL long long
#define Matrix vector<vector<LL>>

const int MOD = 1e9 + 7;

Matrix identity(int dim) {
    Matrix I(dim, vector<LL>(dim, 0));
    for (int i = 0; i < dim; i++)
        I[i][i] = 1;
    return I;
}

Matrix mulMod(Matrix A, Matrix B, int MOD) {
    assert(A.size() != 0);
    assert(B.size() != 0);
    assert(A[0].size() == B.size());

    int n = A.size(), m = B[0].size(), k = B.size();
    Matrix C(n, vector<long long>(m, 0));

    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            for (int p = 0; p < k; p++)
                C[i][j] = (C[i][j] + A[i][p] * B[p][j]) % MOD;

    return C;
}

Matrix matPowMod(Matrix A, LL k, int MOD) {
    assert(A.size() != 0);
    assert(A.size() == A[0].size());
    int dim = A.size();
    if(k == 0) {
        return identity(dim);
    }
    if(k == 1) {
        return A;
    }
    
    Matrix B = matPowMod(A, k / 2, MOD);
    Matrix squaredB = mulMod(B, B, MOD);
    if(k % 2 == 0) {
        return squaredB;
    }
    
    return mulMod(squaredB, A, MOD);
}

int main() {
    LL n = 1000000000000000000LL;

    Matrix trans = {
        {0, 1},
        {1, 1}
    };

    Matrix powered = matPowMod(trans, n - 1, MOD);

    Matrix init = {{0, 1}};

    // [0, 1] * trans^(n-1) = [F(n-1), F(n)]
    Matrix result = mulMod(init, powered, MOD);

    cout << "F(" << n << ") mod " << MOD << " = " << result[0][1] << endl;
    return 0;
}

F(1000000000000000000) mod 1000000007 = 209783453

...

...

...

B là ai? Điều đó có thật sự quan trọng không? Một ngày đẹp trời, một ngày chắc chắn không phải hôm nay, có thể không phải ở quá khứ, có thể không phải ở tương lai, cậu học sinh, hay cậu sinh viên, hay chỉ đơn thuần là một cậu trai, đã giải một bài toán: Problem - 1513C - Codeforces. Đề bài và kết quả kiểm tra được thiết kế để khi chạy với thuật toán đáp án dự kiến của bài toán, nó sẽ tốn gần 1 giây để tính ra kết quả với trường hợp số lớn nhất mà đề bài đã cho. Nhưng, trên bảng điểm, nơi lưu lại dấu vết, hoặc sự ghi nhận kết quả mà những người đã bỏ công sức ra để giải quyết bài toán, tên B cùng với thời gian chạy của thuật toán của cậu ta được ghi rõ trên đó, 0.1 giây. B thật ra không hề giỏi về việc tính toán, nhưng không có nghĩa là cậu chỉ sử dụng sức tính toán của con người của mình. B sẽ nhận ra, hoặc đã nhận ra điều này?