fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define ll long long
  4. #define mod 1000000007
  5. ll MOD=mod;
  6. ll sum(ll A, ll B)
  7. {
  8.         A = (A + MOD) % MOD;
  9.         B = (B + MOD) % MOD;
  10.         ll ans = (A + B) % MOD;
  11.         ans = (ans + MOD) % MOD;
  12.         return ans;
  13. }
  14. ll f(ll a, ll n)
  15. {
  16.         ll res = a, ans = 0;
  17.         while (n)
  18.         {
  19.                 if (n % 2)
  20.                         ans = (ans + res) % MOD;
  21.                 res = (res + res) % MOD;
  22.                 n /= 2;
  23.         }
  24.         return ans;
  25. }
  26. struct matran
  27. {
  28.         ll a[4][4];
  29.         void print()
  30.         {
  31.                 for (ll i = 0; i < 4; i++)
  32.                 {
  33.                         for (ll j = 0; j < 4; j++)
  34.                                 cout << a[i][j] << " ";
  35.                         cout << '\n';
  36.                 }
  37.         }
  38. };
  39. matran mot, M;
  40. struct matran_1
  41. {
  42.         ll a[1][4];
  43.         void print()
  44.         {
  45.                 for (ll i = 0; i < 1; i++)
  46.                 {
  47.                         for (ll j = 0; j < 4; j++)
  48.                                 cout << a[i][j] << " ";
  49.                         cout << '\n';
  50.                 }
  51.         }
  52. };
  53. matran prod(matran A, matran B)
  54. {
  55.         matran C;
  56.         for (ll i = 0; i < 4; i++)
  57.                 for (ll j = 0; j < 4; j++)
  58.                         C.a[i][j] = 0;
  59.         for (ll i = 0; i < 4; i++)
  60.         {
  61.                 for (ll j = 0; j < 4; j++)
  62.                 {
  63.                         for (ll k = 0; k < 4; k++)
  64.                                 C.a[i][j] = sum(C.a[i][j], f(A.a[i][k], B.a[k][j]));
  65.                 }
  66.         }
  67.         return C;
  68. }
  69. matran_1 prod1(matran_1 A, matran B)
  70. {
  71.         matran_1 C;
  72.         for (ll i = 0; i < 1; i++)
  73.                 for (ll j = 0; j < 4; j++)
  74.                         C.a[i][j] = 0;
  75.         for (ll i = 0; i < 1; i++)
  76.                 for (ll j = 0; j < 4; j++)
  77.                         for (ll k = 0; k < 4; k++)
  78.                                 C.a[i][j] = sum(C.a[i][j], f(A.a[i][k], B.a[k][j]));
  79.         return C;
  80. }
  81. matran po(matran A, ll n)
  82. {
  83.         matran res = A, ans = mot;
  84.         while(n){
  85.                 if(n%2) ans = prod(ans,res);
  86.                 res = prod(res,res);
  87.                 n/=2;
  88.         }
  89.         return ans;
  90. }
  91. int main()
  92. {
  93.  
  94.         ll unit[4][4] = {{1, 0, 0, 0}, {0, 1, 0, 0}, {0, 0, 1, 0}, {0, 0, 0, 1}};
  95.         ll MM[4][4] = {{4, 0, 0, 0}, {1, 3, 1, 0}, {0, 2, 0, 0}, {2, 0, 0, 1}};
  96.  
  97.         for (ll i = 0; i < 4; i++)
  98.         {
  99.                 for (ll j = 0; j < 4; j++)
  100.                 {
  101.                         mot.a[i][j] = unit[i][j];
  102.                         M.a[i][j] = MM[i][j];
  103.                 }
  104.         }
  105.         ll tmp[1][4] = {{1, 1, 1, 1}};
  106.         matran_1 initi;
  107.         for (ll i = 0; i < 1; i++)
  108.         {
  109.                 for (ll j = 0; j < 4; j++)
  110.                         initi.a[i][j] = tmp[i][j];
  111.         }
  112.         ll testcase;
  113.         cin>>testcase;
  114.         while(testcase--){
  115.                 ll nn;
  116.                 cin>>nn;
  117.                 matran_1 lala = prod1(initi,po(M,nn));
  118.                 cout<<lala.a[0][0]<<'\n';
  119.         }
  120.         return 0;
  121. }
  122.  
Success #stdin #stdout 0s 4888KB
comments (?)
stdin
copy 
5
1
2
3
6
1000
stdout
copy 
7
35
159
12835
566998663
https://ideone.com/To94Rt
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!