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