https://oj.luyencode.net/problem/BIGFIBO

[utterances-bot]

Chi tiết bài tập - Luyện Code Online

https://luyencode.net/problem/BIGFIBO

[Anptit]

gợi ý cho ai cần: bài này ìm số fibo bằng ma trận nhé

[LeLam2005]

Đây là code của mình, mình áp dụng từ công thức ở trang này https://codeforces.com/blog/entry/14516 với các bạn nếu đọc thì phải hiểu trước đã rồi mới code lại theo cách riêng của mình nhé !

Xem code AC

#include using namespace std; typedef long long ll; const ll M = 1e9 + 7; #define newl "\n" map F; ll f(ll n) { if (F.count(n)) return F[n]; ll k=n/2; if (n%2==0) return F[n] = (f(k)*f(k) + f(k-1)*f(k-1)) % M; else return F[n] = (f(k)*f(k+1) + f(k-1)*f(k)) % M; } int main(){ ll n; F[0]=F[1]=1; while (cin >> n) cout << f(n) << newl; return 0; }

[nhileomao2810]

FiBo bằng nhân ma trận từ đó xây dụng hàm lũy thừa ma trận [[0, 1][1, 1]]

[ThuanNqt]

ứng dụng của ma trận tính số fibonacci thứ N

Xem code AC

```cpp #include using namespace std; typedef long long ll; #define mod 1000000007 struct Matrix{ long long f[2][2]; }; //nạp chồng toán tử nhân ma trận Matrix operator* (Matrix a,Matrix b){ Matrix c; for(int i=0;i<2;i++){ for(int j=0;j<2;j++){ c.f[i][j]=0; for(int k=0;k<2;k++){ c.f[i][j]= (c.f[i][j] + (a.f[i][k]*b.f[k][j])%mod)%mod; } } } return c; } //Dùng chia để trị Matrix powerMod(Matrix a,long long n){ if(n==1) return a; Matrix tmp=powerMod(a,n/2); if(n%2==0) return tmp*tmp; return tmp*tmp*a; } //Khởi tạo giá trị cho ma trận a và tính kết quả long long tinh(long long n){ Matrix a; a.f[0][0]=1; a.f[1][0]=1; a.f[0][1]=1; a.f[1][1]=0; Matrix kq=powerMod(a,n); return kq.f[0][1]; } int main(){ long long n;cin>>n; cout<

[ThuanNqt]

Cách giải dễ hiểu nhất !

Xem code AC

```cpp //Bài này áp dụng ma trận vuông vào tìm số fibonacci #include using namespace std; const long long MAX = 1000000007; //mảng F,M này để lưu ma trận hệ số long long F[2][2], M[2][2]; //Phương thức tính nhân của 2 ma trận (các bạn phải đặt ra các biến riêng lẻ a, b, c, d nhé vì phép tính bên trên có thể thay đổi giá trị ma trận truyền vào ban đầu) void nhanHaiMaTran(long long x[2][2],long long y[2][2]){ long long a = ((x[0][0]*y[0][0]) % MAX + (x[0][1]*y[1][0]) % MAX) % MAX; long long b = ((x[0][0]*y[0][1]) % MAX + (x[0][1]*y[1][1]) % MAX) % MAX; long long c = ((x[1][0]*y[0][0]) % MAX + (x[1][1]*y[1][0]) % MAX) % MAX; long long d = ((x[1][0]*y[0][1]) % MAX + (x[1][1]*y[1][1]) % MAX) % MAX; F[0][0] = a; F[0][1] = b; F[1][0] = c; F[1][1] = d; } //Dùng đệ quy để tính lũy thừa nhị phân của ma trận void luyThuaNhiPhan(long long x[2][2], long long n){ if(n<=1) return; luyThuaNhiPhan(x, n/2); nhanHaiMaTran(x,x); if(n%2 != 0) nhanHaiMaTran(x,M); } void slove(){ //Khởi tạo giá trị ban đầu cho ma trận F và M F[0][0] = F[0][1] = F[1][0] =1; F[1][1] =0; M[0][0] = M[0][1] = M[1][0] =1; M[1][1] =0; long long n; cin>>n; if(n==0) cout<<1; //In ra 1, các bạn đọc kỹ đề bài nhé !! else{ luyThuaNhiPhan(F,n); //gọi hàm lũy thừa nhị phân nhưng phải truyền vào là n vì ta coi số fibonacci thứ nhất trong đề là thứ 2 cout<

[LesdSD]

python cho ai chua lam dc:))

Xem code AC

```py from collections import defaultdict as dfd Fibonacci_list = dfd(int) Mod = 1000000007 def fibonacci(n): if Fibonacci_list[n]: return Fibonacci_list[n] var=n//2 if n % 2 == 0: Fibonacci_list[n]=(fibonacci(var)*fibonacci(var)+fibonacci(var-1)*fibonacci(var-1))%Mod else: Fibonacci_list[n]=(fibonacci(var)*fibonacci(var+1)+fibonacci(var-1)*fibonacci(var))%Mod return Fibonacci_list[n] Fibonacci_list[0]=Fibonacci_list[1]=1 while True: try: n=int(input()) print(fibonacci(n)) except: break