#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] + 10000000000 * 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 + 2 * mod) % mod << '\n';
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Correct |
1 ms |
476 KB |
Output is correct |
| 3 |
Correct |
1 ms |
344 KB |
Output is correct |
| 4 |
Incorrect |
41 ms |
3920 KB |
Output isn't correct |
| 5 |
Incorrect |
62 ms |
5680 KB |
Output isn't correct |
| 6 |
Incorrect |
66 ms |
5324 KB |
Output isn't correct |
| 7 |
Incorrect |
45 ms |
4176 KB |
Output isn't correct |
| 8 |
Correct |
45 ms |
4944 KB |
Output is correct |
| 9 |
Incorrect |
70 ms |
5456 KB |
Output isn't correct |
| 10 |
Incorrect |
81 ms |
5460 KB |
Output isn't correct |
