Submission #995464

#	Time	Username	Problem	Language	Result	Execution time	Memory
995464		vako_p	Relativnost (COCI15_relativnost)	C++14	56 / 140	80 ms	10832 KiB

relativnost

#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;
	if(b == 1) return a % mod;
	ll k = fpow(a, b / 2);
	ll ans = (k * k) % mod;
	if(b % 2) return (ans * a) % mod;
	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];
		a[i] %= mod;
	}
	for(int i = 1; i <= n; i++){
		cin >> b[i];
		b[i] %= mod;
	}
	c[0] = b[1];
	c[1] = a[1];
	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;
		a1 %= mod;
		b1 %= mod;
		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] + 1000000000LL * 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';
	}
}

• Subtask 1: 56 / 140