Tính nhanh Fibo bằng Ma trận

Jun 2nd, 2020
1,135
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. #include <bits/stdc++.h>
2.
3. using namespace std;
4.
5. const long long mod = (long long)(1e9 + 7);
6.
7. typedef vector<vector<long long>> Matrix;
8.
9. Matrix m = {{1, 1}, {1, 0}};
10.
11. Matrix nhan(Matrix a, Matrix b)
12. {
13.     Matrix res = {{0, 0}, {0, 0}};
14.     res[0][0] = ((a[0][0] * b[0][0]) % mod + (a[0][1] * b[1][0] ) % mod ) % mod;
15.     res[0][1] = ((a[0][0] * b[1][0]) % mod + (a[0][1] * b[1][1]) % mod) % mod;
16.     res[1][0] = ((a[1][0] * b[0][0]) % mod + (a[1][1] * b[1][0]) % mod) % mod;
17.     res[1][1] = ((a[1][0] * b[1][0]) % mod + (a[1][1] * b[1][1]) % mod) % mod;
18.
19.     return res;
20. }
21.
22. Matrix Power(Matrix x, int n)
23. {
24.     if (n == 0) return {{1, 0}, {0, 1}};
25.     Matrix t = Power(x, n / 2);
26.     t = nhan(t, t);
27.
28.     if (n % 2 == 0) return t;
29.     return nhan(t, x);
30. }
31.
32. int main()
33. {
34.
35.     cin.tie(0);
36.     ios_base::sync_with_stdio(0);
37.     int n;
38.     cin >> n;
39.     Matrix res = Power(m, n);
40.     cout << res[1][0] << '\n';
41.
42.     return 0;
43. }
RAW Paste Data