# Số Fibonacci và ứng dụng
Số fibonacci là số được định nghĩa như sau:

$$\begin{align}
\begin{cases}
F_0 = 0\\
F_1 = 1\\
F_n = F_{n-1} + F_{n-2}
\end{cases}
\end{align}$$

Và đây là một vài phần tử đầu tiên của nó:

$$0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...$$

Dãy Fibonacci là dãy số kinh điển tìm thấy từ 800 năm trước nên người ta đã tìm được rất nhiều những tính chất hay và đẹp của nó.

Trong khuôn khổ bài viết này, mình chỉ xin trình bày cách tính của số fibonacci thứ n.

**Gọi số fibonacci thứ n là $F[n]$**
**Trong bài viết này mình sẽ sử dụng thư viện `stdc++.h` và namespace `std`:**

#include <bits/stdc++.h>
using namespace std;

## 1. Thuật toán "trâu bò" (brute force):

Từ định nghĩa của nó, ta có thể dễ dàng tính được $F[n]$ bằng cách cho $F[0] = 0, F[1] = 1$ rồi tính lần lượt từ $F[2], \ldots, F[n - 1]$.
Từ đó $F[n] = F[n-1] + F[n-2]$:

const int N = 1000005;
int F[N]; // So fibonacci
int main(){
    F[0] = 0;
    F[1] = 1;
    int n; cin >> n;
    for (int i = 2; i <= n; i++){
        F[i] = F[i - 1] + F[i - 2];
    }
    cout << F[n];
}

Độ phức tạp thời gian: $O(n)$
Độ phức tạp bộ nhớ: $O(n)$

Và để tối ưu về bộ nhớ, chúng ta có thể sử dụng 3 biến thay phiên nhau (để lưu giá trị $F[n], F[n-1], F[n-2]$)

#include <bits/stdc++.h>
using namespace std;

int main(){
    int a = 0;//F[n-2]
    int b = 1;//F[n-1]
    int c = 0;//F[n]
    int n; cin >> n;
    for (int i = 2; i <= n; i++)
    {
        c = a + b;
        a = b;
        b = c;
    }
    cout << c;
}

Độ phức tạp thời gian: $O(n)$
Độ phức tạp bộ nhớ: $O(1)$

## 2. Sử dụng công thức tổng quát
Dãy fibonacci vốn là một dãy truy hồi tuyến tính (cấp $2$) nên cũng có công thức tổng quát:
$$F[n] = \frac{1}{\sqrt{5}}\left[ \left(\frac{1 + \sqrt{5}}{2} \right)^n - \left(\frac{1 - \sqrt{5}}{2} \right)^n\right]$$

Tuy nhiên công thức này ở dưới dạng số vô tỷ, nên khi tính toán trong C++, ta phải sử dụng `double` dẫn đến việc tính toán khó chính xác.

Vì thế công thức này chỉ có ý nghĩa trong việc xấp xỉ độ lớn của $F[n]$:
$\left|\frac{1 - \sqrt{5}}{2} \right| < 1\Rightarrow n$ đủ lớn thì $F[n] \approx \frac{1}{\sqrt{5}} \left(\frac{1 + \sqrt{5}}{2} \right)^n$

## 3. Sử dụng nhân ma trận
### a. Giới thiệu qua về phép nhân ma trận
- Ma trận $m \times n$ là một mảng gồm $m$ hàng $n$ cột. Trong đó phần tử ở hàng $i$ cột $j$ ký hiệu là $a_{ij}$.
Ta có Ma trận $A_{m \times n}$:
$$ \begin{bmatrix} a_{11} & a_{12} & ... & a_{1n} \newline a_{21} & a_{22} & ... & a_{2n} \newline \vdots & \vdots & \ddots & \vdots \newline a_{m1} & a_{m2} & ... & a_{mn} \end{bmatrix} $$
hay
$$ \begin{pmatrix} a_{11} & a_{12} & ... & a_{1n} \newline a_{21} & a_{22} & ... & a_{2n} \newline \vdots & \vdots & \ddots & \vdots \newline a_{m1} & a_{m2} & ... & a_{mn} \end{pmatrix} $$

- Để ma trận $A$ nhân được với ma trận $B$ thì số cột của $A$ phải bằng số hàng của $B$
- Nếu ma trận $A$ có kích thước $(m \times n)$ và ma trận $B$ có kích thước $(n \times p)$, thì ma trận tích $C = A \times B$ có kích thước $(m \times p)$, phần tử đứng ở hàng thứ $i$, cột thứ $j$ xác định bởi công thức:

$C_{ij} = A_{i1} B_{1j} + A_{i2} B_{2j} + … + A_{in} B_{nj} = \displaystyle\sum_{k = 1}^{n} A_{ik} B_{kj}$ (Với $1 \le i \le m; 1 \le j \le p$)
- Minh họa:

### b. Trở lại bài toán
Ta dễ dàng tìm được công thức $F[n]$ dưới dạng nhân ma trận dựa vào định nghĩa trên:
$$\begin{pmatrix} F_{n + 2} \cr F_{n + 1} \cr\end{pmatrix}
= \begin{pmatrix} 1 & 1 \cr 1 & 0 \cr\end{pmatrix} \begin{pmatrix} F_{n+1} \cr F_{n}\cr\end{pmatrix}
= \begin{pmatrix} 1 & 1 \cr 1 & 0 \cr\end{pmatrix}^2 \begin{pmatrix} F_{n} \cr F_{n - 1}\cr\end{pmatrix}
$$
$$=\ldots
= \begin{pmatrix} 1 & 1 \cr 1 & 0 \cr\end{pmatrix}^n \begin{pmatrix} F_{2} \cr F_{1}\cr\end{pmatrix}$$

Hoặc cũng có thể viết:
$$\begin{pmatrix} 1 & 1 \cr 1 & 0 \cr\end{pmatrix} ^ n = \begin{pmatrix} F_{n+1} & F_{n} \cr F_{n} & F_{n-1} \cr\end{pmatrix}$$

Để lưu lại ma trận, ta sẽ sử dụng một `struct matrix` và để tính lũy thừa của ma trận, ta sử dụng cách tính lũy thừa nhanh:

struct matrix {
    long long mat[2][2];
    // Phep nhan ma tran
    matrix friend operator *(const matrix &a, const matrix &b){
        matrix c;
        for (int i = 0; i < 2; i++) {
            for (int j = 0; j < 2; j++) {
                c.mat[i][j] = 0;
                for (int k = 0; k < 2; k++) {
                    c.mat[i][j] += a.mat[i][k] * b.mat[k][j];
                }
            }
        }
        return c;
    }
};

// luy thua ma tran
matrix matpow(matrix base, long long n) {
    matrix ans{ { // ma tran don vi
      {1, 0},
      {0, 1}
    } };
    while (n) {
        if(n&1) //neu n le
            ans = ans*base;
        base = base*base;
        n >>= 1;
    }
    return ans;
}
//so fibonacci thu n
long long fib(int n) {
    matrix base{ {
      {1, 1},
      {1, 0}
    } };
    return matpow(base, n).mat[0][1];
}

Độ phức tạp thời gian: $O(\log n)$

Cách tính này chỉ tính được các số Fibonacci trong giới hạn `long long` hay `unsigned long long` của `C++`.
Để tính các số to hơn, ta dùng số nguyên lớn (bignum) là các số dưới dạng `string` hoặc `vector<int>`.
Nhưng ta phần lớn, với những bài gặp kết quả đầu ra lớn, ta thường được yêu cầu lấy kết quả theo modulo `MOD` (một số nguyên 32-bit). Khi ấy, chỉ cần chỉnh lại một chút hàm nhân 2 ma trận:

        for (int i = 0; i < 2; i++) {
            for (int j = 0; j < 2; j++) {
                c.mat[i][j] = 0;
                for (int k = 0; k < 2; k++) {
                    c.mat[i][j] += (a.mat[i][k] * b.mat[k][j] % MOD);//lay modulo o day
                    c.mat[i][j] %= MOD;//lay modulo o day
                }
            }
        }

## 4. Khử nhân ma trận.
- Dựa vào công thức nhân ma trận
$$\begin{pmatrix} 1 & 1 \cr 1 & 0 \cr\end{pmatrix} ^ n = \begin{pmatrix} F_{n+1} & F_{n} \cr F_{n} & F_{n-1} \cr\end{pmatrix}$$

- Cho $n = 2k$
$$ \begin{pmatrix} F_{2k+1} & F_{2k}\\ F_{2k} & F_{2k-1} \end{pmatrix} = \begin{pmatrix} 1 & 1\\ 1 & 0 \end{pmatrix}^{2k} = \begin{pmatrix} F_{k+1} & F_{k}\\ F_{k} & F_{k-1} \end{pmatrix} ^2 $$

- Từ đó, ta rút ra:
$$ \begin{align} F_{2k+1} &= F_{k+1}^2 + F_{k}^2 \\ F_{2k} &= F_k(F_{k+1}+F_{k-1})\end{align}.$$

Ta sử dụng `map`/`unordered_map` để lưu tại những giá trị đã từng tính:

map<int, long long> F; //so fibonacci thu n
F[0]=F[1]=1;

long long f(int n) {
     if (F.count(n)) return F[n];
     int k=n/2;
     if (n % 2 == 0) { // n=2*k
         return F[n] = (f(k) * f(k) + f(k-1) * f(k-1)) % MOD;
     }
     else { // n=2*k+1
         return F[n] = (f(k) * f(k+1) + f(k-1) * f(k)) % MOD;
     }
}

- Ví dụ khi ta cần tính $F_{k-1}, F_k, F_{k+1}$.
+ Nếu k lẻ, ta cần tính $F_{\frac{k-3}{2}}, F_{\frac{k-1}{2}}, F_{\frac{k+1}{2}}, F_{\frac{k+3}{2}}$
+ Nếu k chẵn, ta cần tính $F_{\frac{k}{2}-1}, F_{\frac{k}{2}}, F_{\frac{k}{2}+1}$
- Dễ thấy, mỗi độ cao ta chỉ cần tính tối đa 4 giá trị, thế nên độ phức tạp thời gian sẽ là $O(\log n)$.
- Cách này giúp chúng ta không phải cài đặt nhân ma trận, tuy nhiên việc tìm ra công thức cũng không dễ. Hơn nữa cách này chỉ dùng được trong các bài toán đếm, nghĩa là nó không thể hoàn toàn thay thế nhân ma trận.

## MỘT SỐ VÍ DỤ
### Ví dụ 1:
Tính tổng n số Fibonacci đầu tiên.

- Nếu như ai "thuộc lòng" những tính chất của dãy Fibonacci thì bài này tất nhiên không thể làm khó chúng ta: $F_1+F_2+…+F_n=F_{n+2}−1$.
Hay tổng quát hơn là $F_1+F_2+…+F_n=F_{n+2}−F_2$ với $F_1=a, F_2=b$.
Sau đó ta chỉ cần nhân ma trận như ở trên.
- Tuy nhiên ta vẫn có một cách dễ nghĩ hơn (*với độ phức tạp thời gian tương đương*) mà không phải tìm lại công thức kia trong tiềm thức của chúng ta.
- Chỉ bằng việc thêm một biến $S_n = F_1+F_2+…+F_n$
Rõ ràng $S_{n + 1} = S_n + F_{n + 1}$ nên ta dựng được công thức:
$$\begin{pmatrix} F_{n + 2} \cr F_{n + 1} \cr S_{n + 1} \end{pmatrix}
= \begin{pmatrix} 1 & 1 & 0 \cr 1 & 0 & 0 \cr 1 & 0 & 1\end{pmatrix} \begin{pmatrix} F_{n+1} \cr F_{n}\cr S_n \end{pmatrix}
$$
- Độ phức tạp về thời gian khi sử dụng công thức hay không đều là $O(\log n)$

### Một số tính chất khác của dãy Fibonacci
**0) $F_1+F_2+…+F_n=F_{n+2}−1$**
**1) $F_{m+n}=F_{m−1}F_{n+1}+F_mF_n$** (Quy nạp với $n$)
Từ tính chất này ta sẽ có vài tính chất khác như:

+ Nếu $n|m$ thì $F_n|F_m$
+ Nếu $F_n$ chia hết cho $F_m$ thì $n$ chia hết cho $m$ $(m>2)$
+ $\gcd(F_m,F_n)=F_{\gcd(m,n)}$
+ Nhờ tính chất này, ta có thể làm được bài sau: [Ước chung lớn nhất của dãy Fibonacci](http://ntucoder.net/Problem/Details/5647)

**2) Dãy Fibonacci theo modulo $n$ sẽ tuần hoàn.**
+ Thật vậy, xét $n^2 + 1$ cặp số Fibonacci liên tiếp theo modulo $n$: $$(F_0,\ F_1),\ (F_1,\ F_2),\ \ldots,\ (F_{n^2},\ F_{n^2 + 1})$$
+ Thương của một số khi chia $n$ có $n$ số dư nên có $n^2$ cặp số dư. Theo nguyên lý Dirichlet thì phải có $2$ cặp $(F_{a},\ F_{a + 1})$ và $(F_{b},\ F_{b + 1})$ với $a \neq b$ sao cho $(F_{a} \bmod n,\ F_{a + 1} \bmod n) = (F_{b} \bmod n,\ F_{b + 1} \bmod n)$.
+ Sử dụng công thức $F_n = F_{n-1} + F_{n-2}$ ta có điều cần chứng minh
+ Đây là một tính chất quan trọng đã từng được sử dụng trong kỳ thi VOI năm 2017: [VOI 2017 - Bài 2](https://hackmd.io/@lD8cRq8_SuefSV17UR3Y-w/HJtWisBb3)

### Ví dụ 2:
[Codeforces - 446C DZY Loves Fibonacci Numbers](https://codeforces.com/problemset/problem/446/C?fbclid=IwAR1R575ZbNnuQWvkV4dDNjRg8wEHunYO-icTCeVEAtNtkQfBx2vAm58MagE)
Xét $F_n$ là số Fibonacci thứ $n$.
Cho một dãy $n$ số nguyên: $a_1, a_2, …, a_n$. Thực hiện $m$ truy vấn, mỗi truy vấn thuộc một trong hai dạng:

Dạng $1:$ $1$ $l$ $r$ : Tăng mỗi phần tử $a_i$ thêm $F_{i - l + 1}$ , trong đó $l \le i \le r$ .
Dạng $2:$ $2$ $l$ $r$ : In ra giá trị của $\sum\limits_{i = l}^{r} a_{i}$ theo modulo $10^9 + 9$ .

#### Lời giải
- Với hai truy vấn này, ta có thể thấy rõ cách sử dụng cây phân đoạn (Segment Tree) kết hợp nhân ma trận với độ phức tạp thời gian $O(m\log n)$
- Tuy nhiên, ta có thể loại bỏ nhân ma trận bằng cách sử dụng "vài kiến thức toán học cơ bản":
+ Đầu tiên là **công thức tổng quát**:
$$F[n] = \frac{1}{\sqrt{5}}\left[ \left(\frac{1 + \sqrt{5}}{2} \right)^n - \left(\frac{1 - \sqrt{5}}{2} \right)^n\right]$$
+ Sau đó để lấy $10^9 + 9$, ta cần làm gì? Nếu như tính $\frac{1}{x} \mod n$, ta nghĩ ngay đến **nghịch đảo modulo** (inversion modulo), thì đến căn thức bậc 2, ta cũng có 1 thứ tương tự - **thặng dư bình phương**: nghĩa ta cần tìm $x$ để $x^2 \equiv 5 \bmod 10^9+9$ . Rồi ta có thể thay $\sqrt5$ bởi $x$ theo modulo này.
+ Và thế là $383008016 \equiv \sqrt 5 \bmod 10^9+9$
+ Thay vào thì được $F_n=276601605(691504013^n-308495997^n) \bmod 10^9+9$
Cái này có thể tính nhanh với "Lũy thừa nhanh".
+ Ở đây, ta có thể dùng công thức này trực tiếp vào segment tree mà không cần nhân ma trận.

## BÀI TẬP ỨNG DỤNG
- Một số bài luyện tập cách tính dãy Fibonacci:
[VNOI - Lát gạch 4](https://oj.vnoi.info/problem/latgach4)
[VNOI - Nhân ma trận - Fibonacci](https://oj.vnoi.info/problem/errichto_matexp_fibonacci)
[Codeforces - 446C DZY Loves Fibonacci Numbers](https://codeforces.com/problemset/problem/446/C?fbclid=IwAR1R575ZbNnuQWvkV4dDNjRg8wEHunYO-icTCeVEAtNtkQfBx2vAm58MagE)
[SPOJ - Tổng Fibonacci](https://www.spoj.com/problems/FIBOSUM/)
[VNOI - Tribonacci](https://oj.vnoi.info/problem/vostribo)
[DMOJ - Tính Fibonacci bản khó](https://dmoj.ca/problem/fibonacci2)

- Một số bài tập áp dụng tính chất dãy Fibonacci:
[VNOI - VOI 2017 - Bài 2](https://hackmd.io/@lD8cRq8_SuefSV17UR3Y-w/HJtWisBb3)
[NTUCoder - Ước chung lớn nhất của dãy Fibonacci](http://ntucoder.net/Problem/Details/5647)
[NTUCoder - Fibonacci 5](http://ntucoder.net/Problem/Details/3299)