Advertisement
Oibek

Fibonacci - Matrix

Feb 4th, 2018
230
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. typedef unsigned long long ull;
  5.  
  6. void power(ull F[2][2], ull n);
  7. void multiply(ull F[2][2], ull M[2][2]);
  8. const ull MOD = 1000000007;
  9.  
  10. ull solve(ull n)
  11. {
  12.     if (n==0) return 0;
  13.  
  14.     ull F[2][2] {{1, 1}, {1, 0}};
  15.     power(F, n-1);
  16.     return F[0][0];
  17. }
  18.  
  19. void power(ull F[2][2], ull n)
  20. {
  21.     if (n==0 or n==1) return;
  22.  
  23.     ull M[2][2] {{1, 1}, {1, 0}};
  24.     power(F, n/2);
  25.     multiply(F, F);
  26.  
  27.     if (n%2!=0)
  28.         multiply(F, M);
  29. }
  30.  
  31. void multiply(ull F[2][2], ull M[2][2])
  32. {
  33.    ull x  = F[0][0]*M[0][0] + F[0][1]*M[1][0];
  34.    ull y  = F[0][0]*M[0][1] + F[0][1]*M[1][1];
  35.    ull z  = F[1][0]*M[0][0] + F[1][1]*M[1][0];
  36.    ull w  = F[1][0]*M[0][1] + F[1][1]*M[1][1];
  37.  
  38.     F[0][0] = x%MOD;
  39.     F[0][1] = y%MOD;
  40.     F[1][0] = z%MOD;
  41.     F[1][1] = w%MOD;
  42. }
  43.  
  44.  
  45. int main() {
  46.     ios_base::sync_with_stdio(0); cin.tie(0), cout.tie(0);
  47.  
  48.     ull n; cin >> n;
  49.     cout << solve(n);
  50.     return 0;
  51. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement