結果
| 問題 |
No.2594 Mix shake!!
|
| コンテスト | |
| ユーザー |
 tko919
|
| 提出日時 | 2023-12-23 04:04:52 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 33,287 bytes |
| コンパイル時間 | 5,931 ms |
| コンパイル使用メモリ | 280,320 KB |
| 最終ジャッジ日時 | 2025-02-18 13:40:35 |
|
ジャッジサーバーID （参考情報） |
judge1 / judge2 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 25 WA * 6 TLE * 1 -- * 53 |
ソースコード
#line 1 "library/Template/template.hpp"
#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=(int)(a);i<(int)(b);i++)
#define ALL(v) (v).begin(),(v).end()
#define UNIQUE(v) sort(ALL(v)),(v).erase(unique(ALL(v)),(v).end())
#define SZ(v) (int)v.size()
#define MIN(v) *min_element(ALL(v))
#define MAX(v) *max_element(ALL(v))
#define LB(v,x) int(lower_bound(ALL(v),(x))-(v).begin())
#define UB(v,x) int(upper_bound(ALL(v),(x))-(v).begin())
using ll=long long int;
using ull=unsigned long long;
const int inf = 0x3fffffff;
const ll INF = 0x1fffffffffffffff;
template<typename T>inline bool chmax(T& a,T b){if(a<b){a=b;return 1;}return 0;}
template<typename T>inline bool chmin(T& a,T b){if(a>b){a=b;return 1;}return 0;}
template<typename T,typename U>T ceil(T x,U y){assert(y!=0); if(y<0)x=-x,y=-y; return (x>0?(x+y-1)/y:x/y);}
template<typename T,typename U>T floor(T x,U y){assert(y!=0); if(y<0)x=-x,y=-y; return (x>0?x/y:(x-y+1)/y);}
template<typename T>int popcnt(T x){return __builtin_popcountll(x);}
template<typename T>int topbit(T x){return (x==0?-1:63-__builtin_clzll(x));}
template<typename T>int lowbit(T x){return (x==0?-1:__builtin_ctzll(x));}
#line 2 "library/Utility/fastio.hpp"
#include <unistd.h>
class FastIO{
static constexpr int L=1<<16;
char rdbuf[L];
int rdLeft=0,rdRight=0;
inline void reload(){
int len=rdRight-rdLeft;
memmove(rdbuf,rdbuf+rdLeft,len);
rdLeft=0,rdRight=len;
rdRight+=fread(rdbuf+len,1,L-len,stdin);
}
inline bool skip(){
for(;;){
while(rdLeft!=rdRight and rdbuf[rdLeft]<=' ')rdLeft++;
if(rdLeft==rdRight){
reload();
if(rdLeft==rdRight)return false;
}
else break;
}
return true;
}
template<typename T,enable_if_t<is_integral<T>::value,int> =0>inline bool _read(T& x){
if(!skip())return false;
if(rdLeft+20>=rdRight)reload();
bool neg=false;
if(rdbuf[rdLeft]=='-'){
neg=true;
rdLeft++;
}
x=0;
while(rdbuf[rdLeft]>='0' and rdLeft<rdRight){
x=x*10+(neg?-(rdbuf[rdLeft++]^48):(rdbuf[rdLeft++]^48));
}
return true;
}
inline bool _read(__int128_t& x){
if(!skip())return false;
if(rdLeft+40>=rdRight)reload();
bool neg=false;
if(rdbuf[rdLeft]=='-'){
neg=true;
rdLeft++;
}
x=0;
while(rdbuf[rdLeft]>='0' and rdLeft<rdRight){
x=x*10+(neg?-(rdbuf[rdLeft++]^48):(rdbuf[rdLeft++]^48));
}
return true;
}
inline bool _read(__uint128_t& x){
if(!skip())return false;
if(rdLeft+40>=rdRight)reload();
x=0;
while(rdbuf[rdLeft]>='0' and rdLeft<rdRight){
x=x*10+(rdbuf[rdLeft++]^48);
}
return true;
}
template<typename T,enable_if_t<is_floating_point<T>::value,int> =0>inline bool _read(T& x){
if(!skip())return false;
if(rdLeft+20>=rdRight)reload();
bool neg=false;
if(rdbuf[rdLeft]=='-'){
neg=true;
rdLeft++;
}
x=0;
while(rdbuf[rdLeft]>='0' and rdbuf[rdLeft]<='9' and rdLeft<rdRight){
x=x*10+(rdbuf[rdLeft++]^48);
}
if(rdbuf[rdLeft]!='.')return true;
rdLeft++;
T base=.1;
while(rdbuf[rdLeft]>='0' and rdbuf[rdLeft]<='9' and rdLeft<rdRight){
x+=base*(rdbuf[rdLeft++]^48);
base*=.1;
}
if(neg)x=-x;
return true;
}
inline bool _read(char& x){
if(!skip())return false;
if(rdLeft+1>=rdRight)reload();
x=rdbuf[rdLeft++];
return true;
}
inline bool _read(string& x){
if(!skip())return false;
for(;;){
int pos=rdLeft;
while(pos<rdRight and rdbuf[pos]>' ')pos++;
x.append(rdbuf+rdLeft,pos-rdLeft);
if(rdLeft==pos)break;
rdLeft=pos;
if(rdLeft==rdRight)reload();
else break;
}
return true;
}
template<typename T>inline bool _read(vector<T>& v){
for(auto& x:v){
if(!_read(x))return false;
}
return true;
}
char wtbuf[L],tmp[50];
int wtRight=0;
inline void _write(const char& x){
if(wtRight>L-32)flush();
wtbuf[wtRight++]=x;
}
inline void _write(const string& x){
for(auto& c:x)_write(c);
}
template<typename T,enable_if_t<is_integral<T>::value,int> =0>inline void _write(T x){
if(wtRight>L-32)flush();
if(x==0){
_write('0');
return;
}
else if(x<0){
_write('-');
if (__builtin_expect(x == std::numeric_limits<T>::min(), 0)) {
switch (sizeof(x)) {
case 2: _write("32768"); return;
case 4: _write("2147483648"); return;
case 8: _write("9223372036854775808"); return;
}
}
x=-x;
}
int pos=0;
while(x!=0){
tmp[pos++]=char((x%10)|48);
x/=10;
}
rep(i,0,pos)wtbuf[wtRight+i]=tmp[pos-1-i];
wtRight+=pos;
}
inline void _write(__int128_t x){
if(wtRight>L-40)flush();
if(x==0){
_write('0');
return;
}
else if(x<0){
_write('-');
x=-x;
}
int pos=0;
while(x!=0){
tmp[pos++]=char((x%10)|48);
x/=10;
}
rep(i,0,pos)wtbuf[wtRight+i]=tmp[pos-1-i];
wtRight+=pos;
}
inline void _write(__uint128_t x){
if(wtRight>L-40)flush();
if(x==0){
_write('0');
return;
}
int pos=0;
while(x!=0){
tmp[pos++]=char((x%10)|48);
x/=10;
}
rep(i,0,pos)wtbuf[wtRight+i]=tmp[pos-1-i];
wtRight+=pos;
}
inline void _write(double x){
ostringstream oss;
oss << fixed << setprecision(15) << double(x);
string s = oss.str();
_write(s);
}
template<typename T>inline void _write(const vector<T>& v){
rep(i,0,v.size()){
if(i)_write(' ');
_write(v[i]);
}
}
public:
FastIO(){}
~FastIO(){flush();}
inline void read(){}
template <typename Head, typename... Tail>inline void read(Head& head,Tail&... tail){
assert(_read(head));
read(tail...);
}
template<bool ln=true,bool space=false>inline void write(){if(ln)_write('\n');}
template <bool ln=true,bool space=false,typename Head, typename... Tail>inline void write(const Head& head,const Tail&... tail){
_write(head);
write<ln,true>(tail...);
if(space)_write(' ');
}
inline void flush(){
fwrite(wtbuf,1,wtRight,stdout);
wtRight=0;
}
};
/**
* @brief Fast IO
*/
#line 3 "sol.cpp"
#line 2 "library/Convolution/ntt.hpp"
template <typename T> struct NTT {
static constexpr int rank2 = __builtin_ctzll(T::get_mod() - 1);
std::array<T, rank2 + 1> root; // root[i]^(2^i) == 1
std::array<T, rank2 + 1> iroot; // root[i] * iroot[i] == 1
std::array<T, std::max(0, rank2 - 2 + 1)> rate2;
std::array<T, std::max(0, rank2 - 2 + 1)> irate2;
std::array<T, std::max(0, rank2 - 3 + 1)> rate3;
std::array<T, std::max(0, rank2 - 3 + 1)> irate3;
NTT() {
T g = 2;
while (g.pow((T::get_mod() - 1) >> 1) == 1) {
g += 1;
}
root[rank2] = g.pow((T::get_mod() - 1) >> rank2);
iroot[rank2] = root[rank2].inv();
for (int i = rank2 - 1; i >= 0; i--) {
root[i] = root[i + 1] * root[i + 1];
iroot[i] = iroot[i + 1] * iroot[i + 1];
}
{
T prod = 1, iprod = 1;
for (int i = 0; i <= rank2 - 2; i++) {
rate2[i] = root[i + 2] * prod;
irate2[i] = iroot[i + 2] * iprod;
prod *= iroot[i + 2];
iprod *= root[i + 2];
}
}
{
T prod = 1, iprod = 1;
for (int i = 0; i <= rank2 - 3; i++) {
rate3[i] = root[i + 3] * prod;
irate3[i] = iroot[i + 3] * iprod;
prod *= iroot[i + 3];
iprod *= root[i + 3];
}
}
}
void ntt(std::vector<T> &a, bool type = 0) {
int n = int(a.size());
int h = __builtin_ctzll((unsigned int)n);
if (type) {
int len = h; // a[i, i+(n>>len), i+2*(n>>len), ..] is transformed
while (len) {
if (len == 1) {
int p = 1 << (h - len);
T irot = 1;
for (int s = 0; s < (1 << (len - 1)); s++) {
int offset = s << (h - len + 1);
for (int i = 0; i < p; i++) {
auto l = a[i + offset];
auto r = a[i + offset + p];
a[i + offset] = l + r;
a[i + offset + p] =
(unsigned long long)(T::get_mod() + l.v - r.v) *
irot.v;
;
}
if (s + 1 != (1 << (len - 1)))
irot *= irate2[__builtin_ctzll(~(unsigned int)(s))];
}
len--;
} else {
// 4-base
int p = 1 << (h - len);
T irot = 1, iimag = iroot[2];
for (int s = 0; s < (1 << (len - 2)); s++) {
T irot2 = irot * irot;
T irot3 = irot2 * irot;
int offset = s << (h - len + 2);
for (int i = 0; i < p; i++) {
auto a0 = 1ULL * a[i + offset + 0 * p].v;
auto a1 = 1ULL * a[i + offset + 1 * p].v;
auto a2 = 1ULL * a[i + offset + 2 * p].v;
auto a3 = 1ULL * a[i + offset + 3 * p].v;
auto a2na3iimag =
1ULL * T((T::get_mod() + a2 - a3) * iimag.v).v;
a[i + offset] = a0 + a1 + a2 + a3;
a[i + offset + 1 * p] =
(a0 + (T::get_mod() - a1) + a2na3iimag) *
irot.v;
a[i + offset + 2 * p] =
(a0 + a1 + (T::get_mod() - a2) +
(T::get_mod() - a3)) *
irot2.v;
a[i + offset + 3 * p] =
(a0 + (T::get_mod() - a1) +
(T::get_mod() - a2na3iimag)) *
irot3.v;
}
if (s + 1 != (1 << (len - 2)))
irot *= irate3[__builtin_ctzll(~(unsigned int)(s))];
}
len -= 2;
}
}
T e = T(n).inv();
for (auto &x : a)
x *= e;
} else {
int len = 0; // a[i, i+(n>>len), i+2*(n>>len), ..] is transformed
while (len < h) {
if (h - len == 1) {
int p = 1 << (h - len - 1);
T rot = 1;
for (int s = 0; s < (1 << len); s++) {
int offset = s << (h - len);
for (int i = 0; i < p; i++) {
auto l = a[i + offset];
auto r = a[i + offset + p] * rot;
a[i + offset] = l + r;
a[i + offset + p] = l - r;
}
if (s + 1 != (1 << len))
rot *= rate2[__builtin_ctzll(~(unsigned int)(s))];
}
len++;
} else {
// 4-base
int p = 1 << (h - len - 2);
T rot = 1, imag = root[2];
for (int s = 0; s < (1 << len); s++) {
T rot2 = rot * rot;
T rot3 = rot2 * rot;
int offset = s << (h - len);
for (int i = 0; i < p; i++) {
auto mod2 = 1ULL * T::get_mod() * T::get_mod();
auto a0 = 1ULL * a[i + offset].v;
auto a1 = 1ULL * a[i + offset + p].v * rot.v;
auto a2 = 1ULL * a[i + offset + 2 * p].v * rot2.v;
auto a3 = 1ULL * a[i + offset + 3 * p].v * rot3.v;
auto a1na3imag =
1ULL * T(a1 + mod2 - a3).v * imag.v;
auto na2 = mod2 - a2;
a[i + offset] = a0 + a2 + a1 + a3;
a[i + offset + 1 * p] =
a0 + a2 + (2 * mod2 - (a1 + a3));
a[i + offset + 2 * p] = a0 + na2 + a1na3imag;
a[i + offset + 3 * p] =
a0 + na2 + (mod2 - a1na3imag);
}
if (s + 1 != (1 << len))
rot *= rate3[__builtin_ctzll(~(unsigned int)(s))];
}
len += 2;
}
}
}
}
vector<T> mult(const vector<T> &a, const vector<T> &b) {
if (a.empty() or b.empty())
return vector<T>();
int as = a.size(), bs = b.size();
int n = as + bs - 1;
if (as <= 30 or bs <= 30) {
if (as > 30)
return mult(b, a);
vector<T> res(n);
rep(i, 0, as) rep(j, 0, bs) res[i + j] += a[i] * b[j];
return res;
}
int m = 1;
while (m < n)
m <<= 1;
vector<T> res(m);
rep(i, 0, as) res[i] = a[i];
ntt(res);
if (a == b)
rep(i, 0, m) res[i] *= res[i];
else {
vector<T> c(m);
rep(i, 0, bs) c[i] = b[i];
ntt(c);
rep(i, 0, m) res[i] *= c[i];
}
ntt(res, 1);
res.resize(n);
return res;
}
};
/**
* @brief Number Theoretic Transform
*/
#line 2 "library/Math/modint.hpp"
template <int mod = 1000000007> struct fp {
int v;
static constexpr int get_mod() { return mod; }
int inv() const {
int tmp, a = v, b = mod, x = 1, y = 0;
while (b)
tmp = a / b, a -= tmp * b, swap(a, b), x -= tmp * y, swap(x, y);
if (x < 0) {
x += mod;
}
return x;
}
fp(ll x = 0) : v(x >= 0 ? x % mod : (mod - (-x) % mod) % mod) {}
fp operator-() const { return fp() - *this; }
fp pow(ll t) {
assert(t >= 0);
fp res = 1, b = *this;
while (t) {
if (t & 1)
res *= b;
b *= b;
t >>= 1;
}
return res;
}
fp &operator+=(const fp &x) {
if ((v += x.v) >= mod)
v -= mod;
return *this;
}
fp &operator-=(const fp &x) {
if ((v += mod - x.v) >= mod)
v -= mod;
return *this;
}
fp &operator*=(const fp &x) {
v = ll(v) * x.v % mod;
return *this;
}
fp &operator/=(const fp &x) {
v = ll(v) * x.inv() % mod;
return *this;
}
fp operator+(const fp &x) const { return fp(*this) += x; }
fp operator-(const fp &x) const { return fp(*this) -= x; }
fp operator*(const fp &x) const { return fp(*this) *= x; }
fp operator/(const fp &x) const { return fp(*this) /= x; }
bool operator==(const fp &x) const { return v == x.v; }
bool operator!=(const fp &x) const { return v != x.v; }
friend istream &operator>>(istream &is, fp &x) { return is >> x.v; }
friend ostream &operator<<(ostream &os, const fp &x) { return os << x.v; }
};
template <typename T> T Inv(ll n) {
static const int md = T::get_mod();
static vector<T> buf({0, 1});
assert(n > 0);
n %= md;
while (SZ(buf) <= n) {
int k = SZ(buf), q = (md + k - 1) / k;
buf.push_back(buf[k * q - md] * q);
}
return buf[n];
}
template <typename T> T Fact(ll n, bool inv = 0) {
static const int md = T::get_mod();
static vector<T> buf({1, 1}), ibuf({1, 1});
assert(n >= 0 and n < md);
while (SZ(buf) <= n) {
buf.push_back(buf.back() * SZ(buf));
ibuf.push_back(ibuf.back() * Inv<T>(SZ(ibuf)));
}
return inv ? ibuf[n] : buf[n];
}
template <typename T> T nPr(int n, int r, bool inv = 0) {
if (n < 0 || n < r || r < 0)
return 0;
return Fact<T>(n, inv) * Fact<T>(n - r, inv ^ 1);
}
template <typename T> T nCr(int n, int r, bool inv = 0) {
if (n < 0 || n < r || r < 0)
return 0;
return Fact<T>(n, inv) * Fact<T>(r, inv ^ 1) * Fact<T>(n - r, inv ^ 1);
}
template <typename T> T nHr(int n, int r, bool inv = 0) {
return nCr<T>(n + r - 1, r, inv);
}
/**
* @brief Modint
*/
#line 4 "library/Convolution/arbitrary.hpp"
using M1 = fp<1045430273>;
using M2 = fp<1051721729>;
using M3 = fp<1053818881>;
NTT<fp<1045430273>> N1;
NTT<fp<1051721729>> N2;
NTT<fp<1053818881>> N3;
const M2 r_12 = M2(M1::get_mod()).inv();
const M3 r_13 = M3(M1::get_mod()).inv();
const M3 r_23 = M3(M2::get_mod()).inv();
const M3 r_1323 = r_13 * r_23;
template <typename T>
vector<T> ArbitraryMult(const vector<int> &a, const vector<int> &b) {
if (a.empty() or b.empty())
return vector<T>();
int n = a.size() + b.size() - 1;
vector<T> res(n);
if (min(a.size(), b.size()) <= 60) {
rep(i, 0, a.size()) rep(j, 0, b.size()) res[i + j] += T(a[i]) * b[j];
return res;
}
vector<int> vals[3];
vector<M1> a1(ALL(a)), b1(ALL(b)), c1 = N1.mult(a1, b1);
vector<M2> a2(ALL(a)), b2(ALL(b)), c2 = N2.mult(a2, b2);
vector<M3> a3(ALL(a)), b3(ALL(b)), c3 = N3.mult(a3, b3);
for (M1 x : c1)
vals[0].push_back(x.v);
for (M2 x : c2)
vals[1].push_back(x.v);
for (M3 x : c3)
vals[2].push_back(x.v);
T w1(M1::get_mod()), w2 = w1 * T(M2::get_mod());
rep(i, 0, n) {
T p = vals[0][i];
T q = (vals[1][i] + M2::get_mod() - p) * r_12.v % M2::get_mod();
T r = ((vals[2][i] + M3::get_mod() - p) * r_1323.v +
(M3::get_mod() - q) * r_23.v) %
M3::get_mod();
res[i] = (p + q * w1 + r * w2);
}
return res;
}
/**
* @brief Arbitrary Mod Convolution
*/
#line 3 "library/Math/bigint.hpp"
template <int D> struct bigint {
using u128 = __uint128_t;
static const int B = pow(10, D);
int sign = 0;
vector<int> v;
static int get_D() { return D; }
static int get_B() { return B; }
bigint(ll x = 0) {
if (x < 0)
x *= -1, sign = 1;
while (x) {
v.push_back(x % B);
x /= B;
}
}
bigint(string s) {
if (s[0] == '-')
s.erase(s.begin()), sign = 1;
int add = 0, cnt = 0, base = 1;
while (s.size()) {
if (cnt == D) {
v.push_back(add);
cnt = 0;
add = 0;
base = 1;
}
add = (s.back() - '0') * base + add;
cnt++;
base *= 10;
s.pop_back();
}
if (add)
v.push_back(add);
}
bigint operator-() const {
bigint res = *this;
res.sign ^= 1;
return res;
}
bigint abs() const {
bigint res = *this;
res.sign = 0;
return res;
}
int &operator[](const int i) { return v[i]; }
int size() const { return v.size(); }
void norm() {
rep(i, 0, v.size() - 1) {
if (v[i] >= 0) {
v[i + 1] += v[i] / B;
v[i] %= B;
} else {
int c = (-v[i] + B - 1) / B;
v[i] += c * B;
v[i + 1] -= c;
}
}
while (!v.empty() and v.back() >= B) {
int c = v.back() / B;
v.back() %= B;
v.push_back(c);
}
while (!v.empty() and v.back() == 0)
v.pop_back();
}
string to_str() const {
string res;
if (v.empty())
return "0";
if (sign)
res += '-';
res += to_string(v.back());
for (int i = v.size() - 2; i >= 0; i--) {
string add;
int w = v[i];
rep(_, 0, D) {
add += ('0' + (w % 10));
w /= 10;
}
reverse(ALL(add));
res += add;
}
return res;
}
friend istream &operator>>(istream &is, bigint<D> &x) {
string tmp;
is >> tmp;
x = bigint(tmp);
return is;
}
friend ostream &operator<<(ostream &os, bigint<D> x) {
os << x.to_str();
return os;
}
bigint &operator<<=(const int &x) {
if (!v.empty()) {
vector<int> add(x, 0);
v.insert(v.begin(), ALL(add));
}
return *this;
}
bigint &operator>>=(const int &x) {
v = vector<int>(v.begin() + min(x, (int)v.size()), v.end());
return *this;
}
bigint &operator+=(const bigint &x) {
if (sign != x.sign) {
*this -= (-x);
return *this;
}
if ((int)v.size() < (int)x.size())
v.resize(x.size(), 0);
rep(i, 0, x.size()) { v[i] += x.v[i]; }
norm();
return *this;
}
bigint &operator-=(const bigint &x) {
if (sign != x.sign) {
*this += (-x);
return *this;
}
if (abs() < x.abs()) {
*this = x - (*this);
sign ^= 1;
return *this;
}
rep(i, 0, x.size()) { v[i] -= x.v[i]; }
norm();
return *this;
}
bigint &operator*=(const bigint &x) {
sign ^= x.sign;
auto v1 = ArbitraryMult<u128>(v, x.v);
u128 add = 0;
v.clear();
for (int i = 0;; i++) {
if (i >= v1.size() and add == 0)
break;
if (i < v1.size())
add += v1[i];
v.push_back(add % B);
add /= B;
}
return *this;
}
bigint &operator/=(const bigint &x) {
bigint a = abs(), b = x.abs();
sign ^= x.sign;
if (a < b)
return *this = bigint();
if (b == bigint(1))
return *this = a;
int d = a.size() - b.size() + 1;
bigint inv(1LL * B * B / b.v.back()), pre;
int cur = 2, bcur = 1;
pre = bigint(0);
while (inv != pre or bcur < b.size()) {
bcur = min(bcur << 1, b.size());
bigint c;
c.v = vector<int>(b.v.end() - bcur, b.v.end());
pre = inv;
inv *= ((bigint(2) << (cur + bcur - 1)) - inv * c);
cur = min(cur << 1, d);
inv.v = vector<int>(inv.v.end() - cur, inv.v.end());
}
inv.v = vector<int>(inv.v.end() - d, inv.v.end());
bigint res = a * inv;
res >>= (a.size());
bigint mul = res * b;
while (mul + b <= a) {
res += bigint(1);
mul += b;
}
v = res.v;
return *this;
}
bigint &operator%=(const bigint &x) {
bigint div = (*this) / x;
(*this) -= div * x;
return *this;
}
bigint square() {
bigint res = *this;
res.sign = 0;
auto v1 = ArbitraryMult<u128>(v, v);
res.v.assign(v1.size(), 0);
rep(i, 0, v1.size()) {
ll val = v1[i];
for (int j = i; val; j++) {
if (j == (int)res.v.size())
res.v.push_back(0);
res.v[j] += val % B;
val /= B;
}
}
res.norm();
return res;
}
bigint mul(ll x) {
bigint res = *this;
if (x < 0)
res.sign ^= 1, x *= -1;
for (int i = res.v.size() - 1; i >= 0; i--)
res.v[i] *= x;
res.norm();
return res;
}
bigint div(ll x) {
bigint res = *this;
if (x < 0)
res.sign ^= 1, x *= -1;
for (int i = res.v.size() - 1; i >= 0; i--) {
if (res.v[i] % x != 0 and i != 0) {
res.v[i - 1] += B * (res.v[i] % x);
}
res.v[i] /= x;
}
res.norm();
return res;
}
bigint operator<<(const int &x) const { return bigint(*this) <<= x; }
bigint operator>>(const int &x) const { return bigint(*this) >>= x; }
bigint operator+(const bigint &x) const { return bigint(*this) += x; }
bigint operator-(const bigint &x) const { return bigint(*this) -= x; }
bigint operator*(const bigint &x) const { return bigint(*this) *= x; }
bigint operator/(const bigint &x) const { return bigint(*this) /= x; }
bigint operator%(const bigint &x) const { return bigint(*this) %= x; }
bool operator<(const bigint &x) const {
if (sign != x.sign)
return sign > x.sign;
if ((int)v.size() != (int)x.size()) {
if (sign)
return (int)x.size() < (int)v.size();
else
return (int)v.size() < (int)x.size();
}
for (int i = v.size() - 1; i >= 0; i--)
if (v[i] != x.v[i]) {
if (sign)
return x.v[i] < v[i];
else
return v[i] < x.v[i];
}
return false;
}
bool operator>(const bigint &x) const { return x < *this; }
bool operator<=(const bigint &x) const { return !(*this > x); }
bool operator>=(const bigint &x) const { return !(*this < x); }
bool operator==(const bigint &x) const {
return !(*this < x) and !(*this > x);
}
bool operator!=(const bigint &x) const { return !(*this == x); }
};
typedef bigint<9> Bigint;
struct Bigfloat {
Bigint v;
int p = 0;
Bigfloat() {}
Bigfloat(const ll &_v) { v = Bigint(_v); }
Bigfloat(const Bigint &_v, int _p = 0) : v(_v), p(_p) {}
void set(int _p) {
if (p < _p) {
v >>= (_p - p);
} else {
v <<= (p - _p);
}
p = _p;
}
Bigint to_int() const {
if (p < 0)
return v >> (-p);
else
return v << p;
}
Bigfloat &operator+=(const Bigfloat &x) {
if (p > x.p)
set(x.p), v += x.v;
else
v += x.v << (x.p - p);
return *this;
}
Bigfloat &operator-=(const Bigfloat &x) {
if (p > x.p)
set(x.p), v -= x.v;
else
v -= x.v << (x.p - p);
return *this;
}
Bigfloat square() {
Bigfloat res = *this;
res.p *= 2;
res.v = res.v.square();
return res;
}
Bigfloat mul(ll x) {
Bigfloat res = *this;
res.v = v.mul(x);
return res;
}
Bigfloat div(ll x) {
Bigfloat res = *this;
res.v = v.div(x);
return res;
}
Bigfloat &operator*=(const Bigfloat &x) {
p += x.p;
v *= x.v;
return *this;
}
Bigfloat &operator/=(const Bigfloat &x) {
p -= x.p;
v /= x.v;
return *this;
}
Bigfloat operator+(const Bigfloat &x) const { return Bigfloat(*this) += x; }
Bigfloat operator-(const Bigfloat &x) const { return Bigfloat(*this) -= x; }
Bigfloat operator*(const Bigfloat &x) const { return Bigfloat(*this) *= x; }
Bigfloat operator/(const Bigfloat &x) const { return Bigfloat(*this) /= x; }
string to_str() {
string res = v.abs().to_str();
int d = Bigint::get_D();
if (p * d > 0)
res += string(p * d, '0');
else if (-p * d >= 1 and -p * d < (int)res.size()) {
res = res.substr(0, (int)res.size() + p * d) + '.' +
res.substr((int)res.size() + p * d);
} else if (-p * d >= (int)res.size())
res = "0." + string(-p * d - (int)res.size(), '0') + res;
if (v.sign) {
res.insert(res.begin(), '-');
}
return res;
}
friend ostream &operator<<(ostream &os, Bigfloat x) {
os << x.to_str();
return os;
}
};
Bigfloat sqrt(ll n, int d) {
Bigfloat res(Bigint((ll)sqrt(1LL * Bigint::get_B() * Bigint::get_B() / n)),
-1),
pre;
int cur = 1;
while (pre.v != res.v) {
cur = min(cur << 1, d);
pre = res;
Bigfloat add = Bigfloat(1) - res.square().mul(n);
add.set(-cur);
res += (res * add).div(2);
res.set(-cur);
}
return res.mul(n);
}
/**
* @brief Big Integer(Float)
*/
#line 2 "library/Math/fraction.hpp"
template <typename T> struct Frac {
T a, b;
Frac(T _a = 0) { init(_a, 1); }
Frac(T _a, T _b) { init(_a, _b); }
Frac &init(T _a, T _b) {
// T g = GCD(_a, _b);
a = _a, b = _b;
if (b < 0)
a = -a, b = -b;
return *this;
}
Frac inv() const { return Frac(b, a); }
Frac operator-() const { return Frac(-a, b); }
Frac &operator+=(const Frac &x) { return init(a * x.b + x.a * b, b * x.b); }
Frac &operator-=(const Frac &x) { return init(a * x.b - x.a * b, b * x.b); }
Frac &operator*=(const Frac &x) { return init(a * x.a, b * x.b); }
Frac &operator/=(const Frac &x) { return init(a * x.b, b * x.a); }
Frac operator+(const Frac &x) const { return Frac(*this) += x; }
Frac operator-(const Frac &x) const { return Frac(*this) -= x; }
Frac operator*(const Frac &x) const { return Frac(*this) *= x; }
Frac operator/(const Frac &x) const { return Frac(*this) /= x; }
bool operator<(const Frac &x) const { return a * x.b < b * x.a; }
bool operator>(const Frac &x) const { return x < *this; }
bool operator<=(const Frac &x) const { return !(x < *this); }
bool operator>=(const Frac &x) const { return !(*this < x); }
bool operator==(const Frac &x) const { return (*this <= x and x <= *this); }
bool operator!=(const Frac &x) const { return !(*this == x); }
T GCD(T a, T b) {
if (b == 0)
return a;
else
return GCD(b, a % b);
}
};
template <typename T> Frac<T> between(const Frac<T> &x, const Frac<T> &y) {
if (x.a < x.b and y.b < y.a)
return Frac(1);
else if (x.b <= x.a) {
T add = floor(x.a / x.b);
return between(x - add, y - add) + add;
} else
return between(y.inv(), x.inv()).inv();
}
/**
* @brief Fraction
* @docs docs/fraction.md
*/
#line 6 "sol.cpp"
FastIO io;
int main() {
auto yes = [&] {
io.write("Yes");
exit(0);
};
auto no = [&] {
io.write("No");
exit(0);
};
int n;
io.read(n);
vector<ll> a(n), b(n), c(n), d(n);
io.read(a, b, c, d);
using fr = Frac<Bigint>;
using P = pair<fr, fr>;
vector<int> ord1(n), ord2(n);
iota(ALL(ord1), 0);
iota(ALL(ord2), 0);
sort(ALL(ord1),
[&](int i, int j) { return fr(b[i], a[i]) < fr(b[j], a[j]); });
sort(ALL(ord2),
[&](int i, int j) { return fr(d[i], c[i]) < fr(d[j], c[j]); });
vector<P> L({{fr(0), fr(0)}}), U = L;
for (auto &i : ord1) {
fr x = L.back().first + fr(a[i]);
fr y = L.back().second + fr(b[i]);
L.push_back({x, y});
}
for (auto &i : ord2) {
fr x = U.back().first + fr(c[i]);
fr y = U.back().second + fr(d[i]);
U.push_back({x, y});
}
rep(i, 0, SZ(U)) {
rep(j, 0, SZ(L) - 1) {
P pq = {L[j + 1].first - L[j].first, L[j + 1].second - L[j].second};
P pr = {U[i].first - L[j].first, U[i].second - L[j].second};
if (pq.first * pr.second - pq.second * pr.first < fr(0))
no();
}
}
if (ord1 == ord2)
yes();
// cerr << "CP3" << '\n';
fr x, y;
rep(i, 0, n - 1) {
auto [xi2, yi2] = L[i + 2];
auto direct = (yi2 - y) / (xi2 - x);
fr mx(inf);
rep(i, 0, SZ(U)) {
if (x < U[i].first and U[i].first < xi2) {
chmin(mx, (U[i].second - y) / (U[i].first - x));
}
}
if (mx == fr(inf) or direct <= mx)
yes();
// pass
auto [xi1, yi1] = L[i + 1];
auto nslope = (yi2 - yi1) / (xi2 - xi1);
if (mx == nslope) {
x = xi1, y = yi1;
continue;
}
auto nx = (mx * x - nslope * xi1 - y + yi1) / (mx - nslope);
auto ny = mx * (nx - x) + y;
// io.write(nx.a.to_str(), nx.b.to_str());
x = nx, y = ny;
}
no();
return 0;
}