Submission #321124

#TimeUsernameProblemLanguageResultExecution timeMemory
321124CodeTiger927Relativnost (COCI15_relativnost)C++14
0 / 140
4061 ms27280 KiB
using namespace std; #include <iostream> #include <cstring> #define MAXN 100005 #define MOD 10007 #define MAXC 25 // Polynomial template struct poly { int coefs[MAXC]; poly() { memset(coefs,0,sizeof(coefs)); coefs[0] = 1; } poly(int a,int b) { memset(coefs,0,sizeof(coefs)); coefs[0] = a % MOD; coefs[1] = b % MOD; } poly operator *(const poly& b) { poly ret; ret.coefs[0] = 0; for(int i = 0;i < MAXC;++i) { for(int j = 0;j < MAXC;++j) { if(i + j < MAXC) ret.coefs[i + j] += coefs[i] * b.coefs[j] % MOD; } } return ret; } int getSum(int n) { int res = 0; for(int i = 0;i <= n;++i) { res += coefs[i]; if(res > MOD) res -= MOD; } return res; } }; poly st[262144]; void update(int x,poly v,int l,int r,int p) { if(l > x || r < x) return; if(l == r) { st[p] = v; return; } int m = (l + r) / 2; update(x,v,l,m,2 * p + 1); update(x,v,m + 1,r,2 * p + 2); st[p] = st[2 * p + 1] * st[2 * p + 2]; return; } void update(int x,poly v) { update(x,v,0,MAXN,0); } poly getPoly(int a,int b,int l,int r,int p) { if(l > b || r < a) return poly(); if(l >= a && r <= b) return st[p]; int m = (l + r) / 2; return getPoly(a,b,l,m,2 * p + 1) * getPoly(a,b,m + 1,r,2 * p + 2); } poly getPoly(int a,int b) { return getPoly(a,b,0,MAXN,0); } int N,C,Q; int arrA[MAXN],arrB[MAXN]; int inv(int a,int b){ return 1 < a ? b - inv(b % a,a) * b / a : 1; } int inv(int a) { return inv(a,MOD); } int main() { int prod = 1; for(int i = 0;i < 262144;++i) { st[i] = poly(); } cin >> N >> C; for(int i = 0;i < N;++i) { cin >> arrA[i]; } for(int i = 0;i < N;++i) { cin >> arrB[i]; update(i,poly(arrB[i],arrA[i])); prod = (prod * (arrA[i] + arrB[i])) % MOD; } cin >> Q; for(int i = 0;i < Q;++i) { int a,b,c; cin >> a >> b >> c; a--; prod = (prod * inv(arrA[a] + arrB[a]) % MOD) * (b + c) % MOD; update(a,poly(b,c)); // cout << prod << " " << getPoly(0,N - 1).getSum(0) << endl; cout << ((prod - getPoly(0,N - 1).getSum(C - 1) + MOD) % MOD) << endl; } }
#Verdict Execution timeMemoryGrader output
Fetching results...