fork download
copy 
  1. #include<math.h>
  2. #include<stdio.h>
  3. #include<stdlib.h>
  4. #include<string.h>
  5. #include<iostream>
  6. #define MOD 1000000007
  7. using namespace std;
  8. unsigned long long A[2][2]={1,1,1,0};
  9. unsigned long long B[2][2]={1,1,1,0};
  10. unsigned long long C[2][2];
  11. int mod_pow1(unsigned long long exponent)
  12. {
  13. if (exponent == 0) return 1;
  14. unsigned long long aux[2][2]={1,0,0,1};
  15. unsigned long long D[2][2];
  16. while(exponent > 1)
  17. {
  18.     if (exponent % 2 != 0)
  19.      {
  20.   D[0][0]=(A[0][0]*aux[0][0] + A[0][1]*aux[1][0]);
  21.   D[1][0]=(A[1][0]*aux[0][0] + A[1][1]*aux[1][0]);
  22.  
  23.   D[0][1]=(A[0][0]*aux[0][1] + A[0][1]*aux[1][1]);
  24.   D[1][1]=(A[1][0]*aux[0][1] + A[1][1]*aux[1][1]);
  25.  
  26.  
  27.     for(int i=0;i<2;++i)
  28.     for(int j=0;j<2;++j)
  29.     aux[i][j]=D[i][j];
  30.  
  31.      }
  32.  
  33.  
  34.     C[0][0]=(A[0][0]*A[0][0] + A[0][1]*A[1][0]);
  35.     C[1][0]=(A[1][0]*A[0][0] + A[1][1]*A[1][0]);
  36.  
  37.     C[0][1]=(A[0][0]*A[0][1] + A[0][1]*A[1][1]);
  38.     C[1][1]=(A[1][0]*A[0][1] + A[1][1]*A[1][1]);
  39.  
  40.  
  41.     for(int i=0;i<2;++i)
  42.     for(int j=0;j<2;++j)
  43.     A[i][j]=C[i][j];
  44.  
  45.         exponent /= 2;
  46. }
  47.  
  48.   D[0][0]=(A[0][0]*aux[0][0] + A[0][1]*aux[1][0]);
  49.   D[1][0]=(A[1][0]*aux[0][0] + A[1][1]*aux[1][0]);
  50.  
  51.   D[0][1]=(A[0][0]*aux[0][1] + A[0][1]*aux[1][1]);
  52.   D[1][1]=(A[1][0]*aux[0][1] + A[1][1]*aux[1][1]);
  53.  
  54.  
  55.  
  56.     for(int i=0;i<2;++i)
  57.     for(int j=0;j<2;++j)
  58.     A[i][j]=D[i][j];
  59.  
  60.  
  61. }
  62. int main()
  63. {
  64.  
  65.  
  66.     int t,g,G;//,r,G;
  67.     unsigned long long r,n;
  68.     scanf("%d",&t);
  69.     //fun();
  70.     while(t--)
  71.     {
  72.         //scanf("%d%d",&n,&g);
  73.         cin>>n;
  74.         if(n==1)
  75.         r=1;
  76.         else if(n==2)
  77.         r=2;
  78.         else
  79.         {
  80.         mod_pow1(n-2);
  81.         r=(2*A[0][0] + A[0][1])%MOD;
  82.         }
  83.  
  84.         cout<<r;
  85.  
  86.     }
  87. }
  88.  
Success #stdin #stdout 0s 2900KB
comments (?)
stdin
copy 
1 999999
stdout
copy 
440160765
https://ideone.com/iCPEyz
language:
C++ (gcc 8.3)
created:
11 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!