Submission #444400

#	Time	Username	Problem	Language	Result	Execution time	Memory
444400		qqspeed20015	Relativnost (COCI15_relativnost)	C++14	140 / 140	1299 ms	5872 KiB

relativnost

#include <iostream>
#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;
}

int main()
{
	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;
        printf("%lld\n",res);
    }
	return 0;
}

Compilation message (stderr)

relativnost.cpp: In function 'void multiply(std::vector<long long int>&, std::vector<long long int>&, std::vector<long long int>&)':
relativnost.cpp:24:23: 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 i = 0; i < a.size(); i++)
      |                     ~~^~~~~~~~~~
relativnost.cpp:28:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   28 |         for (int j = 0; j < b.size(); j++)
      |                         ~~^~~~~~~~~~

• Subtask 1: 140 / 140