fork(4) download 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. #define ll long long
  4. ll MM,MOD;
  5. ll sum(ll A,ll B){
  6.         A=(A+MOD)%MOD;
  7.         B=(B+MOD)%MOD;
  8.         ll ans = (A+B)%MOD;
  9.         ans=(ans+MOD)%MOD;
  10.         return ans;
  11. }
  12. ll f(ll a,ll n){
  13.         ll res=a,ans=0;
  14.         while(n){
  15.                 if(n%2) ans=(ans+res)%MOD;
  16.                 res=(res+res)%MOD;
  17.                 n/=2;
  18.         }
  19.         return ans;
  20. }
  21. struct matran{
  22.         ll a[3][3];
  23.         void print(){
  24.                 for(ll i=0;i<3;i++){
  25.                         for(ll j=0;j<3;j++) cout<<a[i][j]<<" ";
  26.                         cout<<'\n';
  27.                 }
  28.         }
  29. } mot,M;
  30. struct boba{
  31.         ll f_n2,f_n1,f_n;
  32.         void print(){
  33.                 cout<<f_n2<<" "<<f_n1<<" "<<f_n<<'\n';
  34.         }
  35. } init;
  36. matran prod(matran A,matran B){
  37.         matran C;
  38.         for(ll i=0;i<3;i++)
  39.            for(ll j=0;j<3;j++) C.a[i][j]=0;
  40.         for(ll i=0;i<3;i++){
  41.                 for(ll j=0;j<3;j++){
  42.                         for(ll k=0;k<3;k++) C.a[i][j]=sum(C.a[i][j],f(A.a[i][k],B.a[k][j]));
  43.                 }
  44.         }
  45.         return C;
  46. }
  47. matran po(matran A,ll n){
  48.         matran res=A,ans=mot;
  49.         while(n){
  50.                 if(n%2) ans=prod(ans,res);
  51.                 res=prod(res,res);
  52.                 n/=2;
  53.         }
  54.         return ans;
  55. }
  56. boba prod1(boba p,matran A){
  57.         boba ans;
  58.         ans.f_n2=0;
  59.         ans.f_n1=1;
  60.         ans.f_n=0;
  61.         for(ll j=0;j<3;j++){
  62.                 if(j==0){
  63.                         ans.f_n2 = sum(sum(f(p.f_n2,A.a[0][j]),f(p.f_n1,A.a[1][j])),f(p.f_n,A.a[2][j]));               
  64.                 }
  65.                 else if(j==1){
  66.                         ans.f_n1 = sum(sum(f(p.f_n2,A.a[0][j]),f(p.f_n1,A.a[1][j])),f(p.f_n,A.a[2][j])); 
  67.                 }
  68.                 else ans.f_n = sum(sum(f(p.f_n2,A.a[0][j]),f(p.f_n1,A.a[1][j])),f(p.f_n,A.a[2][j]));
  69.         }
  70.         return ans;
  71. }
  72. int main(){
  73.  
  74.      ll tmp[3][3]={ {0,0,1},{1,0,1},{0,1,1}};
  75.      ll donvi[3][3]={{1,0,0},{0,1,0},{0,0,1}};
  76.      for(ll i=0;i<3;i++)
  77.         for(ll j=0;j<3;j++) {
  78.                 M.a[i][j]=tmp[i][j];
  79.                 mot.a[i][j]=donvi[i][j];
  80.                 }
  81.      init.f_n2=1;
  82.      init.f_n1=2;
  83.      init.f_n=4;
  84. //      init.print();
  85.      ll n;
  86.      cin>>n>>MM;
  87.      MOD=MM;
  88.      boba ress = prod1(init,po(M,n-1));
  89.      cout<<ress.f_n2;
  90.  
  91.  
  92. }
Success #stdin #stdout 0s 4708KB
comments (?)
stdin 
5 100
stdout 
13
https://ideone.com/5ZrrNT
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!