Ứng dụng nhân ma trận vào tính số Fibonacci lớn

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

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 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:
p1
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

Trả lời

Thư điện tử của bạn sẽ không được hiển thị công khai. Các trường bắt buộc được đánh dấu *