#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define ub upper_bound
#define lb lower_bound
#define clean(a,s) memset((a),0,sizeof((a)[0])*(s))
#define all(x) (x).begin() , (x).end()
#define fi first
#define se second
#define int long long
using pii = pair<int,int>;
using ll = long long;
const int maxn = 2e5+5;
const int inf = 2e9;
const int mod = 1e4+7;
int n,c,q,a[maxn],b[maxn];
vector<int> t[4*maxn];
void build(int vi,int vl,int vr) {
if(vl == vr) {
t[vi].resize(min(c,2ll));
t[vi][0] = b[vl]%mod;
if(t[vi].size() > 1) t[vi][1] = a[vl]%mod;
return;
}
int mid = (vl+vr)/2;
int sz = min(c,vr-vl+2);
int lsz = min(c,mid-vl+2);
int rsz = min(c,vr-mid+1);
build(2*vi,vl,mid);
build(2*vi+1,mid+1,vr);
t[vi].resize(sz);
for(int i=0;i<lsz;i++)
for(int j=0;j<rsz;j++) {
if(i+j >= sz) break;
t[vi][i+j] += t[2*vi][i]*t[2*vi+1][j]%mod;
t[vi][i+j] %= mod;
}
}
void update(int vi,int vl,int vr,int pos) {
if(vl == vr && vl == pos) {
t[vi][0] = b[vl]%mod;
if(t[vi].size() > 1) t[vi][1] = a[vl]%mod;
return;
}
int mid = (vl+vr)/2;
if(pos <= mid) update(2*vi,vl,mid,pos);
else update(2*vi+1,mid+1,vr,pos);
int sz = min(c,vr-vl+2);
int lsz = min(c,mid-vl+2);
int rsz = min(c,vr-mid+1);
t[vi].assign(sz,0);
for(int i=0;i<lsz;i++)
for(int j=0;j<rsz;j++) {
if(i+j >= sz) break;
t[vi][i+j] += t[2*vi][i]*t[2*vi+1][j]%mod;
t[vi][i+j] %= mod;
}
}
int exp(int p,int k) {
int ret = 1;
while(k) {
if(k&1) ret = (ret*p)%mod;
p = (p*p)%mod;
k >>= 1;
}
return ret;
}
int32_t main () {
//freopen("in","r",stdin); freopen("out","w",stdout);
ios_base::sync_with_stdio(0); cout.tie(0); cin.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];
build(1,1,n);
int mul = 1;
for(int i=1;i<=n;i++) mul = mul*(a[i]+b[i])%mod;
cin >> q;
while(q--) {
int p,aa,bb;
cin >> p >> aa >> bb;
mul *= (aa%mod+bb%mod)%mod;
mul %= mod;
mul *= exp(a[p]+b[p],mod-2);
mul %= mod;
a[p] = aa , b[p] = bb;
update(1,1,n,p);
int ans = 0;
for(int i=0;i<t[1].size();i++) {
//cout << t[1][i] << endl;
ans = (ans+t[1][i])%mod;
}
ans = (mul-ans+2*mod)%mod;
cout << ans << endl;
}
}
Compilation message
relativnost.cpp: In function 'int32_t main()':
relativnost.cpp:94:16: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
94 | for(int i=0;i<t[1].size();i++) {
| ~^~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
19 ms |
19180 KB |
Output is correct |
| 2 |
Correct |
21 ms |
19180 KB |
Output is correct |
| 3 |
Correct |
23 ms |
19180 KB |
Output is correct |
| 4 |
Correct |
415 ms |
25836 KB |
Output is correct |
| 5 |
Correct |
847 ms |
30188 KB |
Output is correct |
| 6 |
Correct |
977 ms |
30828 KB |
Output is correct |
| 7 |
Correct |
601 ms |
27256 KB |
Output is correct |
| 8 |
Correct |
421 ms |
29292 KB |
Output is correct |
| 9 |
Correct |
727 ms |
29120 KB |
Output is correct |
| 10 |
Correct |
1470 ms |
29280 KB |
Output is correct |
