fork download
copy 
  1. #include <iostream>
  2.  
  3. using namespace std;
  4. typedef long long int ll;
  5. const ll MOD = 1000000007;
  6. ll B[5][5] = {{2}, {1}, {4}, {2}, {1}};
  7.  
  8. void Matrix_Multi(ll (*a)[5], ll (*b)[5])
  9. {
  10.     ll tmp[5][5] = {0};
  11.     for (int i = 0; i < 5; i++)
  12.     {
  13.         for (int j = 0; j < 5; j++)
  14.         {
  15.             for (int k = 0; k < 5; k++)
  16.             {
  17.                 tmp[i][j] = (tmp[i][j] + a[i][k] * b[k][j]) % MOD;
  18.             }
  19.         }
  20.     }
  21.     for (int i = 0; i < 5; i++)
  22.     {
  23.         for (int j = 0; j < 5; j++)
  24.         {
  25.             a[i][j] = tmp[i][j];
  26.         }
  27.     }
  28. }
  29. ll Martix_Pow(ll b)
  30. {
  31.     ll A[5][5] =
  32.         {{1, 1, 1, 1, 1},
  33.          {1, 0, 0, 0, 0},
  34.          {0, 0, 1, 2, 1},
  35.          {0, 0, 0, 1, 1},
  36.          {0, 0, 0, 0, 1}};
  37.     ll res[5][5] = {0};
  38.     for (int i = 0; i < 5; i++)
  39.         res[i][i] = 1;
  40.     while (b)
  41.     {
  42.         if (b & 1)
  43.         {
  44.             Matrix_Multi(res, A);
  45.         }
  46.         Matrix_Multi(A, A);
  47.         b >>= 1;
  48.     }
  49.     ll ans = 0;
  50.     for (int i = 0; i < 5; i++)
  51.     {
  52.         ans = (ans + res[0][i] * B[i][0]) % MOD;
  53.     }
  54.     return ans;
  55. }
  56.  
  57. void solve()
  58. {
  59.     int T;
  60.     cin >> T;
  61.     while (T--)
  62.     {
  63.         ll n;
  64.         cin >> n;
  65.         if (n == 0)
  66.         {
  67.             cout << "1\n";
  68.         }
  69.         else if (n == 1)
  70.         {
  71.             cout << "2\n";
  72.         }
  73.         else
  74.         {
  75.             cout << Martix_Pow(n - 1) << "\n";
  76.         }
  77.     }
  78. }
  79.  
  80. int main()
  81. {
  82.     solve();
  83.     return 0;
  84. }
Success #stdin #stdout 0s 15240KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/R9HFFZ
language:
C++14 (clang 8.0)
created:
6 years ago
visibility:
secret

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!