Submission #597839

#	Time	Username	Problem	Language	Result	Execution time	Memory
597839		LeSonnn	Relativnost (COCI15_relativnost)	C++17	0 / 140	1086 ms	1980 KiB

relativnost

#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);
    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();
      |                   ^

• Subtask 1: 0 / 140