#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++)
| ~~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
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 |
