Code mẫu (Hãy code thử trước khi xem):
```
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define vvi vector<vector<int>>
#define FOR(i, a, b) for (int i = a; i < (int)b; i++)
const int MOD = 1e9 + 7;
void input(){
#define taskname "main"
if(fopen(taskname ".inp", "r")){
freopen(taskname ".inp", "r", stdin);
freopen(taskname ".out", "w", stdout);
}
cin.tie(0)->sync_with_stdio(0);
cin.tie(NULL);
cout.tie(NULL);
}
// Hàm solve nhân 2 ma trận 2x2 và trả về kết quả modulo MOD
vvi solve(const vvi& a, const vvi& b) {
return{
{
(a[0][0] * b[0][0] + a[0][1] * b[1][0]) % MOD,
(a[0][0] * b[0][1] + a[0][1] * b[1][1]) % MOD
},
{
(a[1][0] * b[0][0] + a[1][1] * b[1][0]) % MOD,
(a[1][0] * b[0][1] + a[1][1] * b[1][1]) % MOD
}
};
}
// Hàm lt thực hiện phép lũy thừa ma trận (fast exponentiation) trên ma trận m với số mũ n
vvi lt(vvi m, int n) {
// Khởi tạo kết quả là ma trận đơn vị 2x2
vvi res = {{1, 0}, {0, 1}};
while(n > 0) {
// Nếu n lẻ thì nhân res với m
if (n % 2 == 1) {
res = solve(res, m);
}
// Bình phương m
m = solve(m, m);
// Chia n cho 2
n /= 2;
}
return res;
}
// Hàm fibonacci tính số Fibonacci thứ n sử dụng ma trận nhân nhanh
int fibonacci(int n) {
// Trường hợp cơ bản: nếu n = 0 trả về 0, nếu n = 1 trả về 1
if(n == 0) return 0;
if(n == 1) return 1;
// Ma trận chuyển đổi dùng cho tính số Fibonacci
vvi F = {{1, 1}, {1, 0}};
// Lũy thừa ma trận F với số mũ (n - 1)
vvi res = lt(F, n - 1);
// Giá trị số Fibonacci thứ n nằm ở vị trí [0][0] của ma trận kết quả
int ans = res[0][0];
ans %= MOD; // Lấy phần dư theo MOD
return ans;
}
int32_t main(){
input();
int n;
cin >> n;
cout << fibonacci(n);
return 0;
}
```
Chúng ta có thể sử dụng khử nhân ma trận
(Tham khảo thêm ở blog này: https://codeforces.com/blog/entry/14516)
Code mẫu:
```cpp
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int mod = 1e9 + 7;
map<int, int> fibo;
int recur(int n) {
if (fibo.count(n)) return fibo[n];
int k = n / 2;
if (n & 1) return fibo[n] = (recur(k) * recur(k + 1) + recur(k - 1) * recur(k)) % mod;
else return fibo[n] = (recur(k) * recur(k) + recur(k - 1) * recur(k - 1)) % mod;
}
signed main(){
int n; cin >> n;
fibo[0] = fibo[1] = 1;
cout << (n == 0 ? 0 : recur(n-1));
}
MQuang
Created at
2 likes
NguyenKhangNinh_99
Created at
2 likes