#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
const int MOD = 10007;
int add(int a, int b){ a += b; if(a >= MOD) a -= MOD; return a; }
int sub(int a, int b){ return add(a, MOD - b); }
int mul(int a, int b){ return (1LL*a*b)%MOD; }
int pw(int a, int b){
if(b == 0) return 1;
int res = pw(a, b/2);
res = mul(res, res);
if(b%2) res = mul(res, a);
return res;
}
int inv(int a){ return pw(a, MOD - 2); }
const int N = 100000;
int dp[25];
int a[N+5], b[N+5];
int main(){
ios_base::sync_with_stdio(false), cin.tie(0);
cout.precision(10);
cout << fixed;
int n, c;
cin >> n >> c;
c--;
int svi = 1;
int van = 1;
for(int i=1; i<=n; i++) cin >> b[i];
for(int i=1; i<=n; i++) cin >> a[i];
set <int> zeroes;
int jos = 1;
for(int i=1; i<=n; i++){
a[i] %= MOD;
b[i] %= MOD;
if(a[i] == 0){
zeroes.insert(i);
jos = mul(jos, b[i]);
continue;
}
b[i] = mul(b[i], inv(a[i]));
van = mul(van, a[i]);
svi = mul(svi, b[i] + 1);
}
dp[0] = 1;
for(int i=1; i<=n; i++){
if(!a[i]) continue;
for(int j=c; j>=1; j--){
dp[j] = add(dp[j], mul(dp[j-1], b[i]));
}
}
int qrs;
cin >> qrs;
while(qrs--){
int ind, _a, _b;
cin >> ind >> _b >> _a;
_a %= MOD;
_b %= MOD;
if(a[ind]){
van = mul(van, inv(a[ind]));
svi = mul(svi, inv(b[ind] + 1));
for(int j=1; j<=c; j++) dp[j] = sub(dp[j], mul(dp[j-1], b[ind]));
}
else zeroes.erase(ind), jos = mul(jos, inv(b[ind]));
a[ind] = _a;
b[ind] = _b;
if(a[ind]){
_b = mul(_b, inv(_a));
b[ind] = _b;
van = mul(van, a[ind]);
svi = mul(svi, b[ind] + 1);
for(int j=c; j>=1; j--) dp[j] = add(dp[j], mul(dp[j-1], b[ind]));
}
else zeroes.insert(ind), jos = mul(jos, b[ind]);
int res = svi;
for(int j=0; j<=c - int(zeroes.size()); j++) res = sub(res, dp[j]);
if(zeroes.size() > c) cout << "0\n";
else cout << mul(res, mul(van, jos)) << "\n";
}
return 0;
}
Compilation message
relativnost.cpp: In function 'int main()':
relativnost.cpp:84:26: warning: comparison of integer expressions of different signedness: 'std::set<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
84 | if(zeroes.size() > c) cout << "0\n";
| ~~~~~~~~~~~~~~^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
332 KB |
Output is correct |
| 2 |
Correct |
2 ms |
332 KB |
Output is correct |
| 3 |
Correct |
2 ms |
332 KB |
Output is correct |
| 4 |
Correct |
78 ms |
3696 KB |
Output is correct |
| 5 |
Correct |
114 ms |
5072 KB |
Output is correct |
| 6 |
Correct |
106 ms |
4676 KB |
Output is correct |
| 7 |
Correct |
88 ms |
3896 KB |
Output is correct |
| 8 |
Correct |
80 ms |
4220 KB |
Output is correct |
| 9 |
Correct |
116 ms |
5120 KB |
Output is correct |
| 10 |
Correct |
130 ms |
4956 KB |
Output is correct |
