| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 597834 | LeSonnn | Relativnost (COCI15_relativnost) | C++17 | 1085 ms | 2120 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
/**
<=================================================================>
{ *Author:Le Son-Tk2cht }
{ *Spawn:01/10/2006-Ha Tinh City-VN }
{ *School:Ha Tinh High School for the Gifted }
{ (\_/) <----------------------------------> }
{ (•_•) {|Written by LeSonnn-SharkLord-Tk2|} }
{ />💻 <----------------------------------> }
{ }
{ ________________________________ }
{ / (Code) / (Debug) / }
{ /===============================/ }
{ <------------(Choose)------------> }
{ Goal:... }
<=================================================================>
It's never too late to start over
If you're not happy with yesterday,try something different today
Don't stay stuck
Do better
**/
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<unordered_map>
#include<queue>
#define task"relativnost"
using namespace __gnu_pbds;
using namespace std;
typedef long long ll;
typedef long double ld;
typedef unsigned long long llu;
typedef pair<long long,long long>ii;
typedef tree<int,null_type,less<int>,
rb_tree_tag,tree_order_statistics_node_update> indexed_set;
//fastio
#define fast ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define file_inp(_s_) freopen((_s_).c_str(), "r", stdin)
#define file_out(_s_) freopen((_s_).c_str(), "w", stdout)
#pragma GCC optimize ("Ofast")
//struct-----pair
#define mp make_pair
#define fi first
#define se second
//vector
#define pb push_back
#define pf push_front
#define eb emplace_back
#define sz(a) (int)(a.size())
//bit
#define bp __builtin_popcount
#define mask(a) (1LL<<(a))
#define readbit(a,x) ((a>>x)&1)
//loops
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define FOD(i,a,b) for(int i=a;i>=b;i--)
#define FORA(i,a,b) for(int i=a;i<b;i++)
#define FORB(i,a,b) for(int i=a-1;i>=b;i--)
#define REP(a,x) for(auto& a:x)
//endl-----'\n'
#define EL cout<<'\n'
#define ELE cout<<endl
//fast cin-cout
//mazimize-minimize
template<class shark>
inline bool minimize(shark &a,const shark &b)
{
return (a > b ? (a = b),1 : 0);
}
template<class shark>
inline bool maximize(shark &a,const shark &b)
{
return (a < b ? (a = b),1 : 0);
}
template<typename shark>
bool to_maximize(shark &x, const shark &y)
{
if(x<y)
{
x=y;
return true;
}
return false;
}
//fast bp,bit,lcm
long long bpow(long long n,long long m,long long mod)
{
long long res=1;while(m){if(m&1)res=res*n%mod;n=n*n%mod;m>>=1;}
return res;
}
long long getbit(long long val,long long num)
{
return ((val>>num)*1LL);
}
long long lcm(long long a,long long b)
{
return a*b/__gcd(a,b);
}
//===============================================>>
void file(const string FILE="Test")
{
freopen((FILE+".INP").c_str(),"r",stdin);
freopen((FILE+".OUT").c_str(),"w",stdout);
}
//declare
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(i,1,n) 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);
FORA(i,0,q)
{
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;
FORA(i,0,c)
{
res = (res + mod - ans[i]) % mod;
}
res = (res + proAll) % mod;
cout<<res;
}
}
//main
int main()
{
//Written by LeSonnn_
fast
if(fopen(task".inp","r"))
{
freopen(task".inp","r",stdin);
freopen(task".out","w",stdout);
}
ll nt;
for(nt=1;nt--;)
{
solve();
}
}
/**
Input:
okokok
Output:
kokoko
**/
Compilation message (stderr)
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| Fetching results... | ||||