結果

問題 No.187 中華風 (Hard)
ユーザー ShanOveryShanOvery
提出日時 2020-06-01 16:08:06
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 221 ms / 3,000 ms
コード長 9,763 bytes
コンパイル時間 2,274 ms
コンパイル使用メモリ 209,316 KB
実行使用メモリ 8,300 KB
最終ジャッジ日時 2024-11-21 22:06:18
合計ジャッジ時間 5,420 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 5 ms
8,048 KB
testcase_01 AC 4 ms
8,256 KB
testcase_02 AC 115 ms
8,136 KB
testcase_03 AC 113 ms
8,152 KB
testcase_04 AC 134 ms
8,184 KB
testcase_05 AC 133 ms
8,152 KB
testcase_06 AC 134 ms
8,300 KB
testcase_07 AC 133 ms
8,132 KB
testcase_08 AC 119 ms
8,132 KB
testcase_09 AC 118 ms
8,176 KB
testcase_10 AC 118 ms
8,152 KB
testcase_11 AC 221 ms
8,172 KB
testcase_12 AC 134 ms
8,132 KB
testcase_13 AC 57 ms
8,128 KB
testcase_14 AC 57 ms
8,124 KB
testcase_15 AC 105 ms
8,064 KB
testcase_16 AC 106 ms
8,064 KB
testcase_17 AC 5 ms
8,180 KB
testcase_18 AC 5 ms
8,064 KB
testcase_19 AC 4 ms
8,064 KB
testcase_20 AC 102 ms
8,140 KB
testcase_21 AC 3 ms
8,064 KB
testcase_22 AC 133 ms
8,260 KB
testcase_23 AC 4 ms
8,052 KB
testcase_24 AC 4 ms
8,192 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#pragma region Modefs
#define retword "-1"
constexpr long long MAXCOMB = 202020;
constexpr long long MOD = 1000000007;
constexpr long double EPS = 1e-9;
#pragma endregion
//--MACROS---------------------------------
#pragma region Macros
#include <bits/stdc++.h>
#define SORT(x) sort((x).begin(), (x).end())
#define RSORT(x) sort((x).rbegin(), (x).rend())
#define ALL(x) (x).begin(), (x).end()
#define REV(x) reverse(ALL(x))
#define rep(i, n) for (ll i = 0; i < n; i++)
#define reps(i, m, n) for (ll i = m; i < n; i++)
#define repr(i, m, n) for (ll i = m; i >= n; i--)
#define SP << " " <<
#define lwb(x,n) distance(x.begin(),lower_bound(ALL(x),(n)))
#define upb(x,n) distance(x.begin(),upper_bound(ALL(x),(n)))
#define fora(i, ...) if(ll i = -1) for(__VA_ARGS__) if(i++, true)
#ifdef _MY_DEBUG
#define isdebug true
#define CHOOSE(a) CHOOSE2 a
#define CHOOSE2(a0,a1,a2,a3,x,...) x
#define debug_1(x1) cout<<#x1<<": "<<x1<<endl
#define debug_2(x1,x2) cout<<#x1<<": "<<x1<<", "#x2<<": "<<x2<<endl
#define debug_3(x1,x2,x3) cout<<#x1<<": "<<x1<<", "#x2<<": "<<x2<<", "#x3<<": "<<x3<<endl
#define debug_4(x1,x2,x3,x4) cout<<#x1<<": "<<x1<<", "#x2<<": "<<x2<<", "#x3<<": "<<x3<<", "#x4<<": "<<x4<<endl
#define de(...) CHOOSE((__VA_ARGS__,debug_4,debug_3,debug_2,debug_1,~))(__VA_ARGS__)
#else
#define isdebug false
#define de(...)
#endif
using namespace std;
using ll = long long;
using ld = long double;
constexpr ll INF2 = 1000000000000000037;
constexpr ll INF = 1000000007;
constexpr ld PI = 3.1415926535897932384626433832795028L;
using P  = pair<ll,ll>;
using TP  = tuple<ll,ll,ll>;
ll intpow(ll a, ll b){ ll ans = 1; while(b){ if(b & 1) ans *= a; a *= a; b /= 2; } return ans; }
ll overmul(ll a, ll b){ return (b?(a>INF2/b?INF2:a*b):0LL);}
template<class T = ll> using v = vector<T>;
template<class T = ll> using vv = vector<vector<T>>;
template<class T = ll> using vvv = vector<vector<vector<T>>>;
template<class T> bool maxi(T &a, const T &b){ if(a<b){a=b;return 1;}return 0;}
template<class T> bool mini(T &a, const T &b){ if(b<a){a=b;return 1;}return 0;}
template<class T> T sumer(const vector<T>& a){ return accumulate(ALL(a),(T)0); }
template<class T> T miner(const vector<T>& a){ return *min_element(ALL(a)); }
template<class T> T maxer(const vector<T>& a){ return *max_element(ALL(a)); }
template<class T> T ceil(T a, T b) { return a/b + !!(a%b); }
template<class T> ll bs(ll ok, ll ng, T checker){
    while( abs(ok-ng)>1 ){ ll mid = (ok+ng)/2; (checker(mid)?ok:ng) = mid; }
    return ok;
}
template<class T> ld bs2(ld ok, ld ng, T checker){
    rep(i,180){ ld mid = (ok+ng)/2; (checker(mid)?ok:ng) = mid; }
    return ok;
}
template<class T> ll UNIQ(vector<T> &a){ SORT(a);a.erase(unique(ALL(a)),a.end()); return a.size();}
template<class T, class U> ostream &operator<<(ostream &os, const pair<T,U> &pe) { os << pe.first << " " << pe.second; return os;}
template<class T> ostream &operator<<(ostream &os, const v<T> &ve) { rep(i,ve.size()) os<< (i?" ":"")<<ve[i]; return os;}
ll topbit(ll a) { return a==0?-1:63-__builtin_clzll(a);}
ll botbit(ll a) { return a==0?64:__builtin_ctzll(a);}
ll popcount(ll a) { return __builtin_popcountll(a);}
#define dame do {cout<< retword <<"\n"; return;} while(false)
template< int mod >
struct ModInt {
    ll x;
    ModInt() : x(0) {}
    ModInt(ll y) : x(y >= 0 ? ( y<mod ? y : y%mod ) : (mod - (-y) % mod) % mod) {}
    ModInt &operator+=(const ModInt &p) {
        if((x += p.x) >= mod) x -= mod;
        return *this;
    }
    ModInt &operator-=(const ModInt &p) {
        if((x += mod - p.x) >= mod) x -= mod;
        return *this;
    }
    ModInt &operator*=(const ModInt &p) {
        x = (int) (1LL * x * p.x % mod);
        return *this;
    }
    ModInt &operator/=(const ModInt &p) {
        *this *= p.inv();
        return *this;
    }
    ModInt operator-() const { return ModInt(-x); }
    ModInt operator+(const ModInt &p) const { return ModInt(*this) += p; }
    ModInt operator-(const ModInt &p) const { return ModInt(*this) -= p; }
    ModInt operator*(const ModInt &p) const { return ModInt(*this) *= p; }
    ModInt operator/(const ModInt &p) const { return ModInt(*this) /= p; }
    bool operator==(const ModInt &p) const { return x == p.x; }
    bool operator!=(const ModInt &p) const { return x != p.x; }
    bool operator<(const ModInt &p) const {return x < p.x; }

    ModInt operator+(const ll &q) const {return ModInt(*this) += (ModInt)q; }
    ModInt operator-(const ll &q) const {return ModInt(*this) -= (ModInt)q; }
    ModInt operator*(const ll &q) const {return ModInt(*this) *= (ModInt)q; }
    ModInt operator/(const ll &q) const {return ModInt(*this) /= (ModInt)q; }
    bool operator==(const ll &q) const {return x == q; }
    bool operator!=(const ll &q) const {return x != q; }

    ModInt operator++(){ if(++x == mod) x = 0; return *this; }
    ModInt operator--(){ x = (x == 0 ? mod-1 : x-1); return *this; }
    ModInt operator++(int){ const ModInt res(*this); ++*this; return res; }
    ModInt operator--(int){ const ModInt res(*this); --*this; return res; }

    ModInt inv() const {
        int a = x, b = mod, u = 1, v = 0, t;
        while(b > 0) {
            t = a / b;
            swap(a -= t * b, b);
            swap(u -= t * v, v);
        }
        return ModInt(u);
    }

    ModInt pow(ll n, bool inv=false) const {
        ModInt ret(1), mul(x);
        while(n > 0) {
        if(n & 1) ret *= mul;
            mul *= mul;
            n >>= 1;
        }
        if(inv) ret=ret.inv();
        return ret;
    }

    friend ostream &operator<<(ostream &os, const ModInt &p) {
        return os << p.x;
    }
    friend istream &operator>>(istream &is, ModInt &a) {
        ll t;
        is >> t;
        a = ModInt< mod >(t);
        return (is);
    }
};
using mint = ModInt< MOD >;
mint mpow(ll x, ll n, bool inv=false) {
    mint ret(1), mul(x);
    while(n > 0) {
    if(n & 1) ret *= mul;
        mul *= mul;
        n >>= 1;
    }
    if(inv) ret=ret.inv();
    return ret;
}
mint fac[MAXCOMB], finv[MAXCOMB], inv[MAXCOMB];
void cinit() {
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    reps(i, 2, MAXCOMB){
        fac[i] = fac[i - 1] * i;
        inv[i] = inv[MOD%i] * -(MOD/i);
        finv[i] = finv[i - 1] * inv[i];
    }
}
mint cmb(int n, int k){ // 二項係数計算
    if (n < k) return 0;
    if (n < 0 || k < 0) return 0;
    return fac[n] * finv[k] * finv[n-k];
}
#pragma endregion
//--GLOBAL---------------------------------


// mが互いに素でない場合に前処理する。
// modのgcd部分(素因子の共通部分)をとって、指数の大きかったほうの情報量が真に大きいので、そちら側のみ残す。
ll PreGarner(vector<ll> &b, vector<ll> &m, ll mod) {
    ll res = 1;
    rep(i,b.size()) {
        rep(j,i) {
            ll g = gcd(m[i], m[j]); // 素因子の共通部分
            if ((b[i] - b[j]) % g != 0) return -1; // no solution

            // mを共通でない部分にする
            m[i] /= g;
            m[j] /= g;
            // 共通部分 g は、指数の大きい方に振り分ける
            // m[i] がまだもってる因子の1つ以上を gi, ほかは gj に。
            ll gi = gcd(m[i], g), gj = g/gi;
            // iに行くべき gj の因子はgcdで判定できる。これをgiに移す。
            do {
                g = gcd(gi, gj);
                gi *= g, gj /= g;
            } while (g != 1);

            m[i] *= gi, m[j] *= gj; // i 側と j 側に戻す
            // 余り b を再計算
            b[i] %= m[i], b[j] %= m[j];
        }
    }
    for (int i = 0; i < (int)b.size(); ++i) (res *= m[i]) %= mod;
    return res; // lcm % mod を返す
}


// 負の数にも対応した mod (a = -11 とかでも OK)
inline ll getmod(ll a, ll m) {
    ll res = a % m;
    if (res < 0) res += m;
    return res;
}

// 拡張 Euclid の互除法
ll extGCD(ll a, ll b, ll &p, ll &q) {
    if (b == 0) { p = 1; q = 0; return a; }
    ll d = extGCD(b, a%b, q, p);
    q -= a/b * p;
    return d;
}

// 逆元計算 (ここでは a と m が互いに素であることが必要)
ll modinv(ll a, ll m) {
    ll x, y;
    extGCD(a, m, x, y);
    return getmod(x, m); // 気持ち的には x % m だが、x が負かもしれないので
}

// Garner のアルゴリズム, x%MOD, LCM%MOD を求める (m は互いに素でなければならない)
// for each step, we solve "coeffs[k] * t[k] + constants[k] = b[k] (getmod. m[k])"
//      coeffs[k] = m[0]m[1]...m[k-1]
//      constants[k] = t[0] + t[1]m[0] + ... + t[k-1]m[0]m[1]...m[k-2]
ll Garner(vector<ll> b, vector<ll> m, ll mod) {
    m.push_back(mod); // sentinel
    vector<ll> coeffs((int)m.size(), 1);
    vector<ll> constants((int)m.size(), 0);
    for (int k = 0; k < (int)b.size(); ++k) {
        ll t = getmod((b[k] - constants[k]) * modinv(coeffs[k], m[k]), m[k]);
        for (int i = k+1; i < (int)m.size(); ++i) {
            (constants[i] += t * coeffs[i]) %= m[i];
            (coeffs[i] *= m[k]) %= m[i];
        }
    }
    return constants.back();
}
//--MAIN-----------------------------------
void Main() {
    ll N;
    cin>>N;
    v<> A(N),B(N);
    rep(i,N) cin>>A[i]>>B[i];
    bool all0=all_of(ALL(A),[](ll x){return x==0;});
    ll x=PreGarner(A,B,MOD);
    if(all0) cout<< x <<"\n";
    else if(x==-1) cout<< -1 <<"\n";
    else cout<< Garner(A,B,MOD) <<"\n";
}
//--START----------------------------------
int main() {
    cin.tie(nullptr); ios_base::sync_with_stdio(false);
    // ifstream in("input.txt"); cin.rdbuf(in.rdbuf());
    // ofstream out("output.txt"); cout.rdbuf(out.rdbuf());
    cout << fixed << setprecision(15);
    // ll Qkai; cin>>Qkai; rep(QQ,Qkai) Main();
    Main();
}
//-----------------------------------------
0