#include<bits/stdc++.h>
#define TASKNAME "codeforce"
#define pb push_back
#define pli pair<int,int>
#define fi first
#define se second
#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL);
using namespace std;
using ll=long long;
const ll maxN=1e5+10;
const ll inf=1e18;
const ll mod=10007;
ll c;
struct node
{
int dp[20];
node()
{
for(int i=0;i<c;i++) dp[i]=0;
}
node operator+(const node&o)
{
node ans;
for(int i=0;i<c;i++)
{
for(int j=0;j<=i;j++)
{
ans.dp[i]+=1ll*dp[j]*o.dp[i-j]%mod;
if(ans.dp[i]>=mod) ans.dp[i]-=mod;
}
}
return ans;
}
}st[4*maxN];
ll n,a[maxN],b[maxN];
ll pw(ll x,ll y)
{
if(y==0) return 1;
ll x1=pw(x,y/2);
x1=x1*x1%mod;
if(y&1) x1=x1*x%mod;
return x1;
}
void build(ll id=1,ll l=1,ll r=n)
{
if(l==r)
{
st[id]=node();
st[id].dp[0]=b[l];
st[id].dp[1]=a[l];
return;
}
ll mid=l+r>>1;
build(id*2,l,mid);
build(id*2+1,mid+1,r);
st[id]=st[id*2]+st[id*2+1];
}
void update(ll pos,ll val1,ll val2,ll id=1,ll l=1,ll r=n)
{
if(l==r)
{
st[id].dp[0]=val2;
st[id].dp[1]=val1;
return;
}
ll mid=l+r>>1;
if(pos<=mid) update(pos,val1,val2,id*2,l,mid);
else update(pos,val1,val2,id*2+1,mid+1,r);
st[id]=st[id*2]+st[id*2+1];
}
ll q;
void solve()
{
cin >> n >> c;
ll ans=1;
for(int i=1;i<=n;i++) cin >> a[i];
for(int i=1;i<=n;i++) cin >> b[i],ans*=(b[i]+a[i]),ans%=mod;
build();
cin >> q;
for(int i=1;i<=q;i++)
{
ll p,x,y;
cin >> p >> x >> y;
ll sum=(a[p]+b[p])%mod;
ans=ans*pw(sum,mod-2);
ans%=mod;
a[p]=x;
b[p]=y;
ans=ans*(a[p]+b[p]);
ans%=mod;
update(p,x,y);
ll vd=0;
for(int j=0;j<c;j++)
{
vd+=st[1].dp[j];
if(vd>=mod) vd-=mod;
}
if(ans-vd<0) cout << ans-vd+mod<<'\n';
else cout << ans-vd<<'\n';
}
//cout << st[2].dp[2]<<'\n';
}
int main()
{
fastio
//freopen(TASKNAME".INP","r",stdin);
//freopen(TASKNAME".OUT","w",stdout);
solve();
}
Compilation message
relativnost.cpp: In function 'void build(ll, ll, ll)':
relativnost.cpp:53:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
53 | ll mid=l+r>>1;
| ~^~
relativnost.cpp: In function 'void update(ll, ll, ll, ll, ll, ll)':
relativnost.cpp:66:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
66 | ll mid=l+r>>1;
| ~^~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
468 KB |
Output is correct |
| 2 |
Correct |
5 ms |
468 KB |
Output is correct |
| 3 |
Correct |
9 ms |
596 KB |
Output is correct |
| 4 |
Correct |
186 ms |
12052 KB |
Output is correct |
| 5 |
Correct |
498 ms |
22952 KB |
Output is correct |
| 6 |
Correct |
697 ms |
23028 KB |
Output is correct |
| 7 |
Correct |
306 ms |
12184 KB |
Output is correct |
| 8 |
Correct |
184 ms |
22764 KB |
Output is correct |
| 9 |
Correct |
323 ms |
22836 KB |
Output is correct |
| 10 |
Correct |
1060 ms |
22628 KB |
Output is correct |
