fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. #define debug     cout << "ok\n";
  4. #define SQR(x)    (1LL * ((x) * (x)))
  5. #define MASK(i)   (1LL << (i))
  6. #define BIT(x, i) (((x) >> (i)) & 1)
  7. #define fi        first
  8. #define se        second
  9. #define pb        push_back
  10.  
  11. #define mp make_pair
  12. #define pii pair<int,int>
  13. #define pli pair<ll,int>
  14. #define vi vector<int>
  15.  
  16. #define FAST ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
  17.  
  18. typedef long long ll;
  19. typedef unsigned long long ull;
  20. typedef long double ld;
  21. typedef unsigned int ui;
  22.  
  23. using namespace std;
  24.  
  25. const int M = 1e9 + 7;
  26. const int INF = 1e9 + 7;
  27. const ll INFLL = (ll)2e18 + 7LL;
  28. const ld PI = acos(-1);
  29.  
  30. const int dx[] = {1, -1, 0, 0, -1, 1, 1, -1};
  31. const int dy[] = {0, 0, 1, -1, -1, -1, 1, 1};
  32.  
  33. template<class _, class __>
  34.     bool minimize(_ &x, const __ y){
  35.         if(x > y){
  36.             x = y;
  37.             return true;
  38.         } else return false;
  39.     }
  40. template<class _, class __>
  41.     bool maximize(_ &x, const __ y){
  42.         if(x < y){
  43.             x = y;
  44.             return true;
  45.         } else return false;
  46.     }
  47.  
  48. template<class _,class __>
  49.     void Add(_ &x, const __ y) {
  50.         x += y;
  51.         if (x >= M) {
  52.             x -= M;
  53.         }
  54.         return;
  55.     }
  56.  
  57. template<class _,class __>
  58.     void Diff(_ &x, const __ y) {
  59.         x -= y;
  60.         if (x < 0) {
  61.             x += M;
  62.         }
  63.         return;
  64.     }
  65.  
  66. //--------------------------------------------------------------
  67.  
  68. const int szmt = 5;
  69.  
  70. ll n,a,b;
  71.  
  72. int mul (int a,int b) {
  73.     return 1LL*a*b%M;
  74. }
  75.  
  76. struct matrix {
  77.     int val[szmt][szmt];
  78.     matrix() {
  79.         memset(val,0,sizeof(val));
  80.     }
  81. } mt0,mt1,mt2;
  82.  
  83. matrix operator * (matrix & a, matrix & b) {
  84.     matrix res;
  85.     for (int i=0;i<szmt;i++) {
  86.         for (int j=0;j<szmt;j++) {
  87.             for (int k=0;k<szmt;k++) {
  88.                 Add(res.val[i][j],mul(a.val[i][k],b.val[k][j]));
  89.             }
  90.         }
  91.     }
  92.     return res;
  93. }
  94.  
  95. matrix FP(matrix base, ll n) {
  96.     if (n == 0) return mt0;
  97.     if (n == 1) return base;
  98.     matrix tmp = FP(base,n/2);
  99.     tmp = tmp*tmp;
  100.     if (n%2 == 0) return tmp;
  101.     tmp = tmp * base;
  102.     return tmp;
  103. }
  104.  
  105. void sol() {
  106.     for (int i=0;i<szmt;i++) {
  107.         mt0.val[i][i] = 1;
  108.     }
  109.     cin >> a >> b >> n;
  110.     a %= M;
  111.     b %= M;
  112.     if (n == 0) {
  113.         cout << a;
  114.         return;
  115.     }
  116.     if (n == 1) {
  117.         cout << b;
  118.         return;
  119.     }
  120.  
  121. //    mt1.val = { {b,0,0,0,0},
  122. //                {a,0,0,0,0},
  123. //                {12,0,0,0,0},
  124. //                {12,0,0,0,0},
  125. //                {3,0,0,0,0}};
  126.     mt1.val[0][0] = b;
  127.     mt1.val[1][0] = a;
  128.     mt1.val[2][0] = 12;
  129.     mt1.val[3][0] = 12;
  130.     mt1.val[4][0] = 3;
  131. //    mt2.val = { {1,2,1,0,0},
  132. //                {1,0,0,0,0},
  133. //                {0,0,1,1,1},
  134. //                {0,0,0,1,2},
  135. //                {0,0,0,0,1}};
  136.     mt2.val[0][0] = 1;
  137.     mt2.val[0][1] = 2;
  138.     mt2.val[0][2] = 1;
  139.     mt2.val[1][0] = 1;
  140.     mt2.val[2][2] = 1;
  141.     mt2.val[2][3] = 1;
  142.     mt2.val[2][4] = 1;
  143.     mt2.val[3][3] = 1;
  144.     mt2.val[3][4] = 2;
  145.     mt2.val[4][4] = 1;
  146.     mt2 = FP(mt2,n-1);
  147.     mt2 = mt2*mt1;
  148.     cout << mt2.val[0][0];
  149. }
  150.  
  151. int main() {
  152. 	freopen("test.inp","r",stdin);
  153. 	freopen("test.out","w",stdout);
  154. 	FAST
  155. 	int t=1;
  156. //	cin >> t;
  157. 	while (t--) sol();
  158. }
  159.  
Success #stdin #stdout 0.01s 5292KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/MZluzy
language:
C++ (gcc 8.3)
created:
10 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!