Submission #597838

#TimeUsernameProblemLanguageResultExecution timeMemory
597838LeSonnnRelativnost (COCI15_relativnost)C++17
0 / 140
1097 ms1996 KiB
#include <bits/stdc++.h> #define ll long long using namespace std; template <typename _type_> void readInt(_type_ &num) { register char c = getchar(); while(c != '-' && (c < '0' || c > '9')) c = getchar(); bool neg = (c == '-'); if (neg) c = getchar(); for(num = 0; '0' <= c && c <= '9'; c = getchar()) num = (num << 1) + (num << 3) + (c - '0'); if (neg) num = -num; } ll maxC; ll mod = 10007; vector <ll> a, b; void multiply (vector<ll> &a, vector<ll> &b, vector<ll> &prod) { for (int i = 0; i < a.size(); i++) { if (i > maxC) break; for (int j = 0; j < b.size(); j++) { if (i + j <= maxC) prod[i + j] = (prod[i + j] + a[i] * b[j]) % mod; else break; } } } vector <ll> divide(ll left, ll right) { vector <ll> ret(maxC + 1, 0); if (left == right) return vector <ll> {b[left], a[left]}; ll mid = (left + right) / 2; vector <ll> v1 = divide(left, mid); vector <ll> v2 = divide(mid + 1, right); multiply(v1, v2, ret); return ret; } ll modProduct(ll left, ll right) { if (left == right) return (a[left] + b[left]) % mod; ll mid = (left + right) / 2; ll v1 = modProduct(left, mid); ll v2 = modProduct(mid + 1, right); return (v1 * v2) % mod; } ll n, c, q, p; ll power(ll x, ll y) { if (y == 0) return 1; ll p = power(x, y / 2) % mod; p = ((p % mod) * (p % mod)) % mod; return (y % 2 == 0) ? p : (x * p) % mod; } ll modInverse(ll a) { return power(a, mod - 2); } vector <ll> invPoly (vector <ll> coeff) { vector <ll> inversePoly(maxC + 1); inversePoly[0] = modInverse(coeff[0]); for (int i = 1; i <= maxC; i++) inversePoly[i] = (inversePoly[0] * (mod - (coeff[1] * inversePoly[i - 1] % mod))) % mod; return inversePoly; } void solve() { readInt(n);readInt(c); maxC = c; a.assign(n + 1, 0); b.assign(n + 1, 0); for (int i = 1; i <= n; i++) readInt(a[i]); for (int i = 1; i <= n; i++) readInt(b[i]); readInt(q); vector <ll> ans = divide(1, n); ll proAll = modProduct(1, n); for (int i = 0; i < q; i++) { readInt(p); if (b[p] % mod == 0 || (a[p] + b[p]) % mod == 0) { readInt(a[p]); readInt(b[p]); ans.clear(); ans = divide(1, n); proAll = modProduct(1, n); } else { vector <ll> inv = invPoly(vector <ll> {b[p], a[p]}); proAll = (proAll * modInverse(a[p] + b[p])) % mod; readInt(a[p]); readInt(b[p]); vector <ll> mulLinear = {b[p], a[p]}; vector <ll> tmp1(maxC + 1), tmp2(maxC + 1); multiply(ans, inv, tmp1); multiply(tmp1, mulLinear, tmp2); ans.clear(); ans = tmp2; proAll = (proAll * (a[p] + b[p])) % mod; } ll res = 0; for (int i = 0; i < c; i++) res = (res + mod - ans[i]) % mod; res = (res + proAll) % mod; cout<<res; } } //main int main() { //Written by LeSonnn_ ios_base::sync_with_stdio(false); cin.tie(NULL);cout.tie(NULL); if(fopen("relativnost.inp","r")) { freopen("relativnost.inp","r",stdin); freopen("relativnost.out","w",stdout); } ll nt; for(nt=1;nt--;) { solve(); } } /** Input: okokok Output: kokoko **/

Compilation message (stderr)

relativnost.cpp: In function 'void readInt(_type_&)':
relativnost.cpp:7:19: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
    7 |     register char c = getchar();
      |                   ^
relativnost.cpp: In function 'void multiply(std::vector<long long int>&, std::vector<long long int>&, std::vector<long long int>&)':
relativnost.cpp:20:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   20 |     for (int i = 0; i < a.size(); i++)
      |                     ~~^~~~~~~~~~
relativnost.cpp:24:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   24 |         for (int j = 0; j < b.size(); j++)
      |                         ~~^~~~~~~~~~
relativnost.cpp: In instantiation of 'void readInt(_type_&) [with _type_ = long long int]':
relativnost.cpp:81:14:   required from here
relativnost.cpp:7:19: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
    7 |     register char c = getchar();
      |                   ^
relativnost.cpp: In function 'int main()':
relativnost.cpp:130:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  130 |         freopen("relativnost.inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
relativnost.cpp:131:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  131 |         freopen("relativnost.out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...