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