fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define FNAME "CNTINVERSE"
  3. using namespace std;
  4. const int MAXN = 501;
  5. typedef long long ll;
  6. const ll MOD = 1e15 + 7;
  7.  
  8. void fastip() {
  9.     ios_base::sync_with_stdio(0);
  10.     cin.tie(0); cout.tie(0);
  11.     if (fopen(FNAME".inp", "r")) {
  12.         freopen(FNAME".inp", "r", stdin);
  13.         freopen(FNAME".out", "w", stdout);
  14.     }
  15. }
  16.  
  17. int t;
  18.  
  19. struct fibo{
  20.     long long t[4][4] = {
  21.         {1,1,0,0},  
  22.         {0,1,1,1},  
  23.         {0,1,0,0},      
  24.         {0,0,1,0},
  25.     };
  26.     fibo operator * (const fibo &m) const{
  27.         fibo res;
  28.         for(int i = 0; i < 4 ; i++){
  29.             for(int j = 0; j < 4 ; j++){
  30.                 long long sum = 0;
  31.                 for(int k = 0; k < 4 ; k++){
  32.                     sum = (sum % MOD + (t[i][k] % MOD * m.t[k][j] % MOD) % MOD) % MOD;
  33.                 }
  34.                 res.t[i][j] = sum % MOD;
  35.             }
  36.         }
  37.         return res;
  38.     }
  39. };
  40.  
  41. fibo indian_pow(fibo base, long long n){
  42.     if(n == 1){
  43.         return base;
  44.     }
  45.     fibo k = indian_pow(base, n / 2);
  46.     if(n % 2 == 0){
  47.         return k * k;
  48.     }else{
  49.         return k * k * base;
  50.     }
  51. }
  52.  
  53. int main(){
  54.     fastip();
  55.  
  56.     cin >> t;
  57.  
  58.     while(t--){
  59.         long long n;
  60.         cin >> n;
  61.         if (n == 1) {
  62.             cout << 1 << endl;
  63.         } else if (n == 2) {
  64.             cout << 3 << endl;
  65.         } else if (n == 3) {
  66.             cout << 6 << endl;
  67.         } else {
  68.             fibo k;
  69.             fibo res = indian_pow(k , n - 2);
  70.             cout << (res.t[0][0] * 3 + res.t[0][1] * 3 + res.t[0][2] * 2 + res.t[0][3] * 1) % MOD  << endl;
  71.         }   
  72.     }
  73.     return 0;
  74. }
Success #stdin #stdout 0s 5324KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/XR5xes
language:
C++ (gcc 8.3)
created:
19 hours 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!