oj.uz

답안 #995453

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
995453 2024-06-09T06:13:42 Z vako_p Relativnost (COCI15_relativnost) C++14
56 / 140
 81 ms 5680 KB 
#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';
	}
}

Subtask #1
56.0 / 140.0

# 결과 실행 시간 메모리 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