SHARE
TWEET

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

vovanhoangtuan Jun 2nd, 2020 1,056 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
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
Top