fork(1) download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. #define ll long long 
  4. struct matran{
  5.     ll a[2][2];
  6.     void print(){
  7.             for(ll i=0;i<2;i++){
  8.                     for(ll j=0;j<2;j++) cout<<a[i][j]<<" ";
  9.                     cout<<'\n';
  10.             }
  11.     }
  12. };
  13. matran mot;
  14. struct cap{
  15.    ll u,u_plus_1;
  16.    void print(){
  17.            cout<<u<<" "<<u_plus_1<<'\n';
  18.    }
  19. };
  20. matran prod(matran A,matran B){
  21.         matran anss;
  22.         anss.a[0][0]=A.a[0][0]*B.a[0][0] + A.a[0][1] * B.a[1][0];
  23.         anss.a[0][1]=A.a[0][0]*B.a[0][1] + A.a[0][1] * B.a[1][1];
  24.         anss.a[1][0]=A.a[1][0]*B.a[0][0] + A.a[1][1] * B.a[1][0];
  25.         anss.a[1][1]=A.a[1][0]*B.a[0][1] + A.a[1][1] * B.a[1][1];
  26.         return anss;
  27. }
  28. matran po(matran X,ll n){
  29.         matran res = X, ans = mot;
  30.         while(n){
  31.                 if(n%2) ans = prod(ans,res);
  32.                 res = prod(res,res);
  33.                 n/=2;
  34.         }
  35.         return ans;
  36. }
  37. cap prod1(cap pp, matran X){
  38.         cap ans;
  39.         ans.u = pp.u * X.a[0][0]+pp.u_plus_1 * X.a[1][0];
  40.         ans.u_plus_1 =  pp.u * X.a[1][0]+pp.u_plus_1 * X.a[1][1];
  41.         return ans;
  42. }
  43. int main(){
  44.  
  45.         ll a,b,nn;
  46.         cin>>a>>b;
  47.         cin>>nn;
  48.  
  49.         cap init;
  50.         init.u = a;
  51.         init.u_plus_1 = b;
  52.         matran M;
  53.         M.a[0][0]=0;
  54.         M.a[0][1]=-1;
  55.         M.a[1][0]=1;
  56.         M.a[1][1]=2;
  57.         mot.a[0][0]=1;
  58.         mot.a[0][1]=0;
  59.         mot.a[1][0]=0;
  60.         mot.a[1][1]=1;
  61.  
  62.         matran res = po(M,nn-1);
  63.         cap ansss = prod1(init,res);
  64.         cout<<ansss.u<<'\n';
  65.  
  66.  
  67.  
  68. }
Success #stdin #stdout 0s 4988KB
comments (?)
stdin
copy 
3 1
1
stdout
copy 
3
https://ideone.com/0e5sgW
language:
C++ (gcc 8.3)
created:
3 years 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!