fork download
copy 
  1. /// Msaa el 5ra
  2. #pragma GCC optimize("Ofast,unroll-loops,no-stack-protector,fast-math")
  3.  
  4. #include <bits/stdc++.h>
  5.  
  6. using namespace std;
  7.  
  8. #define pb push_back
  9. #define F first
  10. #define S second
  11. #define f(i, a, b) for (int i = a; i < b; i++)
  12. #define all(a) a.begin(), a.end()
  13. #define rall(a) a.rbegin(), a.rend()
  14. #define sz(x) (int)(x).size()
  15. #define mp(x, y) make_pair(x, y)
  16. #define popCnt(x) (__builtin_popcountll(x))
  17. // #define int ll
  18.  
  19. using ll = long long;
  20. using ii = pair<int, int>;
  21. using ull = unsigned long long;
  22.  
  23. const int N = 4e5 + 5;
  24. const int M = 4e5 + 5;
  25. const int A = 26;
  26. const int LG = 19;
  27. const int MOD =
  28.         // (119 << 23) + 1;
  29.         1e9 + 7;
  30. const long double PI = acos(-1);
  31. const long double EPS = 1e-7;
  32.  
  33. const ll MAX = 1e15;
  34.  
  35. const int ms = int(1e6) + 20;
  36.  
  37. using Matrix = array<array<int, 101>, 101>;
  38.  
  39. // Matrix multiplication
  40. Matrix multiply(const Matrix &a, const Matrix &b, ll m) {
  41.     Matrix result;
  42.     f(i, 0, m)f(j, 0, m)result[i][j] = 0;
  43.     for (int i = 0; i < m; ++i) {
  44.         for (int j = 0; j < m; ++j) {
  45.             for (int k = 0; k < m; ++k) {
  46.                 result[i][j] = (result[i][j] + 1ll * a[i][k] * b[k][j]) % MOD;
  47.             }
  48.         }
  49.     }
  50.     return result;
  51. }
  52.  
  53. vector<Matrix> allPowers;
  54.  
  55. vector<long long> mul(vector<long long> F, Matrix &Tn, int m) {
  56.     reverse(F.begin(), F.end());
  57.  
  58.     vector<long long> result(m, 0);
  59.     for (int i = 0; i < m; ++i) {
  60.         for (int j = 0; j < m; ++j) {
  61.             result[i] = (result[i] + 1ll * Tn[i][j] * F[j]) % MOD;
  62.         }
  63.     }
  64.     return result;
  65. }
  66.  
  67.  
  68. void preprocess(int m) {
  69.     Matrix T;
  70.     f(i, 0, m)f(j, 0, m)T[i][j] = 0;
  71.  
  72.     for (int i = 0; i < m; ++i) {
  73.         T[0][i] = 1; // First row is all ones
  74.     }
  75.     for (int i = 1; i < m; ++i) {
  76.         T[i][i - 1] = 1; // Sub-diagonal is all ones
  77.     }
  78.     allPowers.push_back(T);
  79.     for (int i = 0; i < 60; i++) {
  80.         T = allPowers.back();
  81.         allPowers.push_back(multiply(T, T, m));
  82.     }
  83. }
  84.  
  85. // Function to compute terms f[n-m], f[n-m+1], ..., f[n-1]
  86. vector<long long> getLastTerms(const vector<long long> &initial, ll n, ll m) {
  87.     // Transition matrix
  88.  
  89.     // Exponentiate the transition matrix
  90.  
  91.     // Initial state vector
  92.  
  93.  
  94.     n -= m;
  95.     vector<long long> F = initial;
  96.     for (int i = 0; i < 60; i++) {
  97.         if (((n >> i) & 1)) {
  98.             F = mul(F, allPowers[i], m);
  99.             reverse(all(F));
  100.         }
  101.     }
  102.     return F;
  103. }
  104.  
  105. ll m, n, q;
  106.  
  107. void doWork() {
  108.  
  109.  
  110.     cin >> m >> n >> q;
  111.     preprocess(m);
  112.  
  113.     vector<ll> init(m);
  114.     for (int i = 0; i < m; i++) cin >> init[i], init[i] = (init[i] + MOD) % MOD;
  115.     vector<pair<ll, ll>> vec;
  116.     f(i, 0, q) {
  117.         ll x, y;
  118.         cin >> x >> y;
  119.         y = (y + MOD) % MOD;
  120.         vec.push_back({x, y});
  121.     }
  122.     sort(all(vec));
  123.     if (vec.back().F == n || m == 1) {
  124.         cout << vec.back().S << endl;
  125.         return;
  126.     }
  127.     ll last_index = m;
  128.     // for (int n=1; n <= 50; n++) {
  129.     //     cout << n << endl;
  130.     //     auto p =getLastTerms(init, m + n - last_index, m);
  131.     //     for (auto x : p)    cout << x << " ";
  132.     //     cout << endl;
  133.     // }
  134.     for (auto [k, v]: vec) {
  135.         auto new_init = getLastTerms(init, (k - last_index - 1) + m, m);
  136.         new_init.erase(new_init.begin());
  137.         new_init.push_back(v);
  138.         init = new_init;
  139.         last_index = k;
  140.     }
  141.  
  142.     cout << getLastTerms(init, m + n - last_index, m).back() << "\n";
  143.  
  144. }
  145.  
  146. int32_t main() {
  147.     ios_base::sync_with_stdio(0);
  148.     cin.tie(0);
  149.     int t = 1;
  150.     // cin >> t;
  151.     while (t--) {
  152.         doWork();
  153.     }
  154. }
Success #stdin #stdout 0.01s 6088KB
comments (?)
stdin
copy 
2 2 1
1 1
1 1
stdout
copy 
172833445
https://ideone.com/V21xft
language:
C++ (gcc 8.3)
created:
1 day 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!