답안 #444400

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
444400 2021-07-14T01:37:48 Z qqspeed20015 Relativnost (COCI15_relativnost) C++14
140 / 140
1299 ms 5872 KB
#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

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++)
      |                         ~~^~~~~~~~~~
# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 204 KB Output is correct
2 Correct 3 ms 300 KB Output is correct
3 Correct 5 ms 332 KB Output is correct
4 Correct 321 ms 4104 KB Output is correct
5 Correct 627 ms 5872 KB Output is correct
6 Correct 1043 ms 5568 KB Output is correct
7 Correct 454 ms 4348 KB Output is correct
8 Correct 297 ms 4980 KB Output is correct
9 Correct 671 ms 5804 KB Output is correct
10 Correct 1299 ms 5456 KB Output is correct