# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
995464 | vako_p | Relativnost (COCI15_relativnost) | C++14 | 80 ms | 10832 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#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';
}
}
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |