fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. typedef long long ll;
  4. const ll mod = 1e9 + 7;
  5.  
  6. ll add(ll a, ll b) { 
  7.     return ((a % mod) + (b % mod)) % mod; 
  8. }
  9. ll mul(ll a, ll b) { 
  10.     return ((a % mod) * (b % mod)) % mod; 
  11. }
  12. ll sub(ll a, ll b) { 
  13.     return ((a % mod) - (b % mod) + mod) % mod; 
  14. }
  15.  
  16. class Matrix {
  17. public:
  18.     ll r, c;
  19.     vector<vector<ll>> mat;
  20.     Matrix(ll rows, ll cols, ll init = 0) {
  21.         r = rows;
  22.         c = cols;
  23.         mat = vector<vector<ll>>(rows, vector<ll>(cols, init));
  24.     }
  25.     static Matrix identity(ll n) {
  26.         Matrix I(n, n, 0);
  27.         for (ll i = 0; i < n; i++)
  28.             I.mat[i][i] = 1;
  29.         return I;
  30.     }
  31.     Matrix operator+(const Matrix& other) const {
  32.         Matrix res(r, c);
  33.         for (ll i = 0; i < r; i++) {
  34.             for (ll j = 0; j < c; j++) {
  35.                 res.mat[i][j] = add(mat[i][j], other.mat[i][j]);
  36.             }
  37.         }
  38.         return res;
  39.     }
  40.     Matrix& operator+=(const Matrix& other) {
  41.         for (ll i = 0; i < r; i++) {
  42.             for (ll j = 0; j < c; j++) {
  43.                 mat[i][j] = add(mat[i][j], other.mat[i][j]);
  44.             }
  45.         }
  46.         return *this;
  47.     }
  48.     Matrix operator*(const Matrix& other) const {
  49.         Matrix res(r, other.c, 0);
  50.         for (ll i = 0; i < r; i++) {
  51.             for (ll j = 0; j < other.c; j++) {
  52.                 ll sum = 0;
  53.                 for (ll k = 0; k < c; k++) {
  54.                     sum = add(sum, mul(mat[i][k], other.mat[k][j]));
  55.                 }
  56.                 res.mat[i][j] = sum;
  57.             }
  58.         }
  59.         return res;
  60.     }
  61.     Matrix& operator*=(const Matrix& other) {
  62.         *this = *this * other;
  63.         return *this;
  64.     }
  65.     Matrix pow(ll n) const {
  66.         Matrix base = *this;
  67.         Matrix result = Matrix::identity(r);
  68.         while (n > 0) {
  69.             if (n & 1) result *= base;
  70.             base *= base;
  71.             n >>= 1;
  72.         }
  73.         return result;
  74.     }
  75. };
  76.  
  77. int main() {
  78.     ios_base::sync_with_stdio(false);
  79.     cin.tie(nullptr);
  80.     cout.tie(nullptr);
  81.  
  82.     ll m, N, Q;
  83.     cin >> m >> N >> Q;
  84.     vector<ll> a(m);
  85.     for (auto &x : a)
  86.         cin >> x;
  87.  
  88.     // Build the companion matrix for f(i) = ∑(previous m numbers)
  89.     Matrix orig(m, m, 0);
  90.     for (int j = 0; j < m; j++) {
  91.         orig.mat[0][j] = 1;  
  92.     }
  93.     for (int i = 1; i < m; i++) {
  94.         orig.mat[i][i - 1] = 1;
  95.     }
  96.  
  97.     // Base state vector: [f(m), f(m-1), ..., f(1)]^T
  98.     Matrix base(m, 1, 0);
  99.     for (int i = 0; i < m; i++) {
  100.         base.mat[i][0] = a[m - 1 - i];
  101.     }
  102.  
  103.     vector<pair<ll, ll>> v;
  104.     for (int i = 0; i < Q; i++) {
  105.         ll j, f;
  106.         cin >> j >> f;
  107.         // Ensure the forced value is in the range [0, mod)
  108.         v.push_back({j, (f % mod + mod) % mod});
  109.     }
  110.  
  111.     ll prev = m; // current index computed
  112.     sort(v.begin(), v.end());
  113.     for (auto &p : v) {
  114.         ll j = p.first, forcedVal = p.second;
  115.         if (j <= prev)
  116.             continue;
  117.         // Jump from 'prev' to forced index j with matrix exponentiation
  118.         Matrix R = orig.pow(j - prev);
  119.         R *= base;
  120.         // Update the state vector: override f(j) with forced value,
  121.         // and keep the rest computed as:
  122.         // New state should be [f(j)_forced, f(j-1)_computed, ..., f(j-m+1)_computed]^T.
  123.         vector<ll> temp(m, 0);
  124.         temp[0] = forcedVal;
  125.         // Fix: use R.mat[k][0], not R.mat[k-1][0]
  126.         for (int k = 1; k < m; k++)
  127.             temp[k] = R.mat[k][0];
  128.         for (int i = 0; i < m; i++)
  129.             base.mat[i][0] = temp[i];
  130.         prev = j;
  131.     }
  132.  
  133.     ll ans;
  134.     if (N <= prev) {
  135.         if (N <= m)
  136.             ans = ((a[N - 1] % mod) + mod) % mod;
  137.         else 
  138.             ans = base.mat[0][0]; // already computed for N = prev
  139.     } else {
  140.         Matrix R = orig.pow(N - prev);
  141.         R *= base;
  142.         ans = R.mat[0][0];
  143.     }
  144.  
  145.     cout << ans << '\n';
  146.     return 0;
  147. }
Success #stdin #stdout 0.01s 5312KB
comments (?)
stdin
copy 
2 8 1
1 1
5 1
stdout
copy 
9
https://ideone.com/m1Nsno
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!