fork download
copy 
  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.  
  59.         for(ll j=0;j<3;j++){
  60.                 if(j==0){
  61.                         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]));               
  62.                 }
  63.                 else if(j==1){
  64.                         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])); 
  65.                 }
  66.                 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]));
  67.         }
  68.         return ans;
  69. }
  70. int main(){
  71.     // freopen("input.txt","r",stdin);
  72.     // freopen("output.txt","w",stdout);
  73.     ll tc;
  74.     cin>>tc;
  75.     for(ll u=1;u<=tc;u++){
  76.      ll tmp[3][3]={ {2,1,0},{0,0,1},{1,0,0}};
  77.      ll donvi[3][3]={{1,0,0},{0,1,0},{0,0,1}};
  78.      for(ll i=0;i<3;i++)
  79.         for(ll j=0;j<3;j++) {
  80.                 M.a[i][j]=tmp[i][j];
  81.                 mot.a[i][j]=donvi[i][j];
  82.                 }
  83.      init.f_n2=4;
  84.      init.f_n1=2;
  85.      init.f_n=1;
  86. //      init.print();
  87.      ll n;
  88.      MM = 10007;
  89.      cin>>n;
  90.      MOD=MM;
  91.      if(n==1){
  92.          cout<<"Case "<<u<<": "<<1<<'\n';
  93.          continue;
  94.      }
  95.      if(n==2){
  96.          cout<<"Case "<<u<<": "<<2<<'\n';
  97.          continue;
  98.      }
  99.      boba ress = prod1(init,po(M,n-2));
  100.      ll aans = (ress.f_n2%MOD-(ress.f_n1%MOD)+MOD)%MOD;
  101.      cout<<"Case "<<u<<": "<<aans<<'\n';
  102.     }
  103. }
Success #stdin #stdout 0s 5568KB
comments (?)
stdin
copy 
2
3
10
stdout
copy 
Case 1: 5
Case 2: 1255
https://ideone.com/bho7ql
language:
C++14 (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!