Submission #1267418

#TimeUsernameProblemLanguageResultExecution timeMemory
1267418canhnam357Relativnost (COCI15_relativnost)C++20
140 / 140
1467 ms21952 KiB
#include <bits/stdc++.h> using namespace std; const int mod = 1e4 + 7; int power(int a, int b) { int res = 1; while (b > 0) { if (b & 1) { res = 1ll * res * a % mod; } a = 1ll * a * a % mod; b >>= 1; } return res; } int mul(int a, int b) { return 1ll * a * b % mod; } int add(int a, int b) { return (a + b) % mod; } int sub(int a, int b) { return (a - b + mod) % mod; } int divide(int a, int b) { return 1ll * a * power(b, mod - 2) % mod; } int k, st[1 << 18][20]{}; void update(int p, int a, int b, int id, int l, int r) { if (l == r) { st[id][0] = b; st[id][1] = a; return; } int mid = (l + r) >> 1; if (p <= mid) update(p, a, b, id << 1, l, mid); else update(p, a, b, id << 1 | 1, mid + 1, r); for (int i = 0; i < k; i++) st[id][i] = 0; for (int i = 0; i < k; i++) { for (int j = 0; j <= i; j++) { st[id][i] = add(st[id][i], mul(st[id << 1][j], st[id << 1 | 1][i - j])); } } } int main() { ios_base::sync_with_stdio(0); cin.tie(0); int n; cin >> n >> k; vector<int> a(n + 1), b(n + 1); for (int i = 1; i <= n; i++) cin >> a[i]; for (int i = 1; i <= n; i++) cin >> b[i]; int ans = 1; for (int i = 1; i <= n; i++) { ans = mul(ans, add(a[i], b[i])); update(i, a[i], b[i], 1, 1, n); } int q; cin >> q; while (q--) { int p, va, vb; cin >> p >> va >> vb; update(p, va, vb, 1, 1, n); ans = divide(ans, add(a[p], b[p])); a[p] = va; b[p] = vb; ans = mul(ans, add(a[p], b[p])); int tot = 0; for (int i = 0; i < k; i++) { tot = add(tot, st[1][i]); } cout << sub(ans, tot) << '\n'; } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...