Submission #597837

# Submission time Handle Problem Language Result Execution time Memory
597837 2022-07-17T01:54:31 Z LeSonnn Relativnost (COCI15_relativnost) C++17
0 / 140
1097 ms 2020 KB
/**
    <=================================================================>
    {     *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|}            }
    {      />ff       <---------------------------------->            }
    {                                                                 }
    {                ________________________________                 }
    {               /    (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"testa"
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(ll 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 (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_
    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

relativnost.cpp:25:9: warning: ISO C++11 requires whitespace after the macro name
   25 | #define task"testa"
      |         ^~~~
relativnost.cpp: In function 'void readInt(_type_&)':
relativnost.cpp:107:19: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
  107 |     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:120:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  120 |     for (int i = 0; i < a.size(); i++)
      |                     ~~^~~~~~~~~~
relativnost.cpp:124:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  124 |         for (int j = 0; j < b.size(); j++)
      |                         ~~^~~~~~~~~~
relativnost.cpp: In instantiation of 'void readInt(_type_&) [with _type_ = long long int]':
relativnost.cpp:181:14:   required from here
relativnost.cpp:107:19: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
  107 |     register char c = getchar();
      |                   ^
relativnost.cpp: In function 'void file(std::string)':
relativnost.cpp:100:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  100 |     freopen((FILE+".INP").c_str(),"r",stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
relativnost.cpp:101:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  101 |     freopen((FILE+".OUT").c_str(),"w",stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
relativnost.cpp: In function 'int main()':
relativnost.cpp:229:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  229 |         freopen(task".inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
relativnost.cpp:230:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  230 |         freopen(task".out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 340 KB Output isn't correct
2 Incorrect 2 ms 340 KB Output isn't correct
3 Incorrect 4 ms 340 KB Output isn't correct
4 Incorrect 268 ms 1348 KB Output isn't correct
5 Incorrect 526 ms 2020 KB Output isn't correct
6 Incorrect 861 ms 2000 KB Output isn't correct
7 Incorrect 365 ms 1492 KB Output isn't correct
8 Incorrect 222 ms 1776 KB Output isn't correct
9 Incorrect 542 ms 1836 KB Output isn't correct
10 Incorrect 1097 ms 1768 KB Output isn't correct