Submission #995447

#TimeUsernameProblemLanguageResultExecution timeMemory
995447vako_pRelativnost (COCI15_relativnost)C++14
56 / 140
90 ms5460 KiB
#include <bits/stdc++.h> using namespace std; #define ll long long #define pb push_back const int mxN = 1e6 + 5; ll n,a[mxN],b[mxN],mod = 10007,C,c[50],c1[50],x[50]; ll fpow(ll a, ll b){ if(b == 0) return 1; ll k = fpow(a, b / 2); ll ans = k * k % mod; if(b % 2) return (ans * a) % mod; else return ans; } int main(){ ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); cin >> n >> C; for(int i = 1; i <= n; i++) cin >> a[i]; for(int i = 1; i <= n; i++) cin >> b[i]; c[0] = b[1] % mod; c[1] = a[1] % mod; for(int i = 2; i <= n; i++){ for(int j = 0; j < C; j++){ c1[j] = c[j] * b[i] % mod; if(j != 0) c1[j] = (c1[j] + c[j - 1] * a[i]) % mod; } for(int j = 0; j < C; j++) c[j] = c1[j]; } ll ans = 1; for(int i = 1; i <= n; i++) ans = ans * (a[i] + b[i]) % mod; ll q; cin >> q; while(q--){ ll idx, a1, b1; cin >> idx >> a1 >> b1; ans = (ans * fpow((a[idx] + b[idx]), mod - 2)) % mod; ll bmod = fpow(b[idx], mod - 2); x[0] = c[0] * bmod % mod; for(int i = 1; i < C; i++){ x[i] = ((c[i] - x[i - 1] * a[idx]) % mod + mod) % mod * bmod % mod; } ll ans1 = 0; a[idx] = a1; b[idx] = b1; for(int j = 0; j < C; j++){ c[j] = x[j] * b[idx] % mod; if(j != 0) c[j] = (c[j] + x[j - 1] * a[idx]) % mod; ans1 = (c[j] + ans1) % mod; } ans = ans * (a[idx] + b[idx]) % mod; cout << (ans - ans1 + mod) % mod << '\n'; } }
#Verdict Execution timeMemoryGrader output
Fetching results...