Advertisement
luanaamorim

Untitled

Mar 29th, 2021
47
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 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