#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
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++)
| ~~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
340 KB |
Output isn't correct |
| 2 |
Incorrect |
3 ms |
340 KB |
Output isn't correct |
| 3 |
Incorrect |
4 ms |
340 KB |
Output isn't correct |
| 4 |
Incorrect |
245 ms |
1276 KB |
Output isn't correct |
| 5 |
Incorrect |
509 ms |
1984 KB |
Output isn't correct |
| 6 |
Incorrect |
853 ms |
2024 KB |
Output isn't correct |
| 7 |
Incorrect |
362 ms |
1508 KB |
Output isn't correct |
| 8 |
Incorrect |
227 ms |
1764 KB |
Output isn't correct |
| 9 |
Incorrect |
523 ms |
1952 KB |
Output isn't correct |
| 10 |
Incorrect |
1080 ms |
1788 KB |
Output isn't correct |
