Advertisement
luanaamorim

Untitled

Mar 29th, 2021
81
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.39 KB | None | 0 0
  1. #include <iostream>
  2. #include <queue>
  3. #include <string>
  4. #include <algorithm>
  5. #include <vector>
  6. #include <cmath>
  7. #include <iomanip>
  8. #include <map>
  9. #include <cstring>
  10. #define ll long long
  11. #define INF 99999999
  12. #define MAX 2
  13. #define MOD 1000000007
  14. #define par pair<int, int>
  15. #define all(v) (v.begin(), v.end())
  16. #define lsb(x) (x & -x)
  17. #define _ ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  18.  
  19. using namespace std;
  20.  
  21. int a, b, n;
  22.  
  23. struct matrix
  24. {
  25.     ll m[MAX][MAX];
  26. };
  27.  
  28. matrix resp, p;
  29.  
  30. matrix mult(matrix a, matrix b)
  31. {
  32.     matrix ans;
  33.     for (int i = 0; i < MAX; i++)
  34.         for (int j = 0; j < MAX; j++)
  35.         {
  36.             ans.m[i][j] = 0;
  37.             for (int k = 0; k < MAX; k++)  
  38.                 ans.m[i][j] = (ans.m[i][j] + ((a.m[i][k]*b.m[k][j]) % MOD)) % MOD;
  39.         }
  40.    
  41.     return ans;
  42. }
  43.  
  44. matrix fexpo(matrix a, ll n)
  45. {
  46.     matrix ans;
  47.     for (int i = 0; i < MAX; i++)
  48.         for (int j = 0; j < MAX; j++)
  49.             ans.m[i][j] = (i==j);
  50.  
  51.     while (n)
  52.     {
  53.         if (n&1) ans = mult(ans, a);
  54.         a = mult(a, a);
  55.         n>>=1LL;
  56.     }
  57.     return ans;
  58. }
  59.  
  60. int main()
  61. {_
  62.     cin >> a >> b >> n;
  63.     p.m[0][0] = 1, p.m[0][1] = -1, p.m[1][0] = 1, p.m[1][1] = 0;
  64.     p = fexpo(p, n - 2);
  65.     resp.m[0][0] = b, resp.m[1][0] = a, resp.m[0][1] = resp.m[1][1] = 0;
  66.     resp = mult(resp, p);
  67.     cout << resp.m[0][0] << endl;
  68. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement