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