02/10/2018, 15:04
Ứ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ố ...
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 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
#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;
}
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; } |
Chị ơi, chị có thể viết code bài này mà không dùng hàm toán tử không ạ