Nhân ma trận được ứng dụng rất nhiều đặc biệt là dùng để tính số Fibonacci lớn rất nhanh, hiệu quả rất nhiều so với các phương pháp duyệt thông thường.
Link submit online: MINIGAME22.3:FIBO
Nội dung bài viết
1. Đề bài ứng dụng nhân ma trận tính Fibonacci
Dãy Fibonacci là dãy vô hạn các số tự nhiên bắt đầu bằng hai phần tử 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ó.
Công thức truy hồi của dãy Fibonacci là:
Nhập vào tập tin fibo.inp số nguyên dương n.
Tính số Fibonacci thứ n.
In ra tập tin fibo.out phần dư của kết quả khi chia cho 109+7.
Lưu ý:
• Subtask 1: 1 ≤ n ≤ 50.• Subtask 2: 1 ≤ n ≤ 106.• Subtask 3: 1 ≤ n ≤ 1012.
2. Hướng dẫn dùng nhân ma trận tính Fibonacci
Nếu bạn for trâu để giải quyết bài này thì bạn không thể accept full test được vì bị Time limit chính vì vậy để giải quyết được bài toán này với độ phức tạp mong muốn, bạn phải ứng dụng nhân ma trận vào để giải quyết bài toán này.
Công thức:
Lưu ý: F0, F1 là 2 số đầu tiên của dãy Fibonacci
Kết hợp thêm lũy thừa nhanh cho phép toán ma trận ((0,1),(1,1))^T
Độ phức tạp thuật toán Log(N)
3. Code dụng nhân ma trận tính Fibonacci
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 | #include <bits/stdc++.h> using namespace std; const long long base = 1000000007; struct MaTran { long long c[2][2]; MaTran() { c[0][0]=0; c[0][1]=1; c[1][0]=1; c[1][1]=1; } }; MaTran operator * (MaTran a, MaTran b) { MaTran res; for (int i=0; i<=1; i++) for (int j=0; j<=1; j++) { res.c[i][j] = 0; for (int k=0; k<=1; k++) res.c[i][j] = (res.c[i][j]+a.c[i][k]*b.c[k][j])%base; } return res; } MaTran powermod (MaTran a, long long n) { if (n==1) return a; if (n%2!=0) return powermod(a,n-1)*a; MaTran tmp = powermod(a,n/2); return tmp*tmp; } int main() { freopen("fibo.inp","r",stdin); freopen("fibo.out","w",stdout); long long n; cin >> n; MaTran A; A = powermod(A,n); cout << A.c[0][1]; return 0; } |
Bài viết liên quan
- DHLOCO spoj – Trò chơi lò cò
- ANT spoj – Kiến
- MYSTERY spoj – Số huyền bí
- BCCOM spoj PTIT – Số nén tối giản
- P151PROA spoj , CF #292 (Div. 2) C. Drazil and Factorial
- BCSEQ1 PTIT spoj – Đoạn số có tổng bằng nhau
- hướng dẫn EXPAR – spoj
- Giải đề thi Lập trình hướng đối tượng UIT – Đề HK2 2016-2017
- [Codeforces] 750A – New Year and Hurry
- Viết chương trình tính tổ hợp Ckn, và xuất ra tam giác pascal
anh ơi, em không hiểu chỗ toán tử *. Anh có thể viết hàm mà không phải hàm toán tử được không ạ ?
Bạn chỉ rõ dòng nào đi bạn, chứ ở trên chỉ là nhân , còn dấu . để gọi tên phương thức là viết dạng hướng đối tượng thôi bạn