結果
| 問題 | No.2008 Super Worker |
| ユーザー |
 rogi52
|
| 提出日時 | 2022-10-16 22:16:06 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 75 ms / 2,000 ms |
| コード長 | 15,730 bytes |
| コンパイル時間 | 2,681 ms |
| コンパイル使用メモリ | 215,744 KB |
| 最終ジャッジ日時 | 2025-02-08 07:20:42 |
|
ジャッジサーバーID （参考情報） |
judge4 / judge2 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 33 |
ソースコード
#include <bits/stdc++.h>#define rep(i,n) for(int i = 0; i < (n); i++)using namespace std;typedef long long ll;template<int MOD> struct Fp {long long val;constexpr Fp(long long v = 0) noexcept : val(v % MOD) { if (val < 0) val += MOD; }constexpr int getmod() const { return MOD; }constexpr Fp operator - () const noexcept { return val ? MOD - val : 0; }constexpr Fp operator + (const Fp& r) const noexcept { return Fp(*this) += r; }constexpr Fp operator - (const Fp& r) const noexcept { return Fp(*this) -= r; }constexpr Fp operator * (const Fp& r) const noexcept { return Fp(*this) *= r; }constexpr Fp operator / (const Fp& r) const noexcept { return Fp(*this) /= r; }constexpr Fp& operator += (const Fp& r) noexcept {val += r.val;if (val >= MOD) val -= MOD;return *this;}constexpr Fp& operator -= (const Fp& r) noexcept {val -= r.val;if (val < 0) val += MOD;return *this;}constexpr Fp& operator *= (const Fp& r) noexcept {val = val * r.val % MOD;return *this;}constexpr Fp& operator /= (const Fp& r) noexcept {long long a = r.val, b = MOD, u = 1, v = 0;while (b) {long long t = a / b;a -= t * b, swap(a, b);u -= t * v, swap(u, v);}val = val * u % MOD;if (val < 0) val += MOD;return *this;}constexpr bool operator == (const Fp& r) const noexcept {return this->val == r.val;}constexpr bool operator != (const Fp& r) const noexcept {return this->val != r.val;}constexpr bool operator < (const Fp& r) const noexcept {return this->val < r.val;}friend constexpr istream& operator >> (istream& is, Fp<MOD>& x) noexcept {is >> x.val;x.val %= MOD;if (x.val < 0) x.val += MOD;return is;}friend constexpr ostream& operator << (ostream& os, const Fp<MOD>& x) noexcept {return os << x.val;}friend constexpr Fp<MOD> modpow(const Fp<MOD>& a, long long n) noexcept {if (n == 0) return 1;auto t = modpow(a, n / 2);t = t * t;if (n & 1) t = t * a;return t;}};namespace NTT {long long modpow(long long a, long long n, int mod) {long long res = 1;while (n > 0) {if (n & 1) res = res * a % mod;a = a * a % mod;n >>= 1;}return res;}long long modinv(long long a, int mod) {long long b = mod, u = 1, v = 0;while (b) {long long t = a / b;a -= t * b, swap(a, b);u -= t * v, swap(u, v);}u %= mod;if (u < 0) u += mod;return u;}int calc_primitive_root(int mod) {if (mod == 2) return 1;if (mod == 167772161) return 3;if (mod == 469762049) return 3;if (mod == 754974721) return 11;if (mod == 998244353) return 3;int divs[20] = {};divs[0] = 2;int cnt = 1;long long x = (mod - 1) / 2;while (x % 2 == 0) x /= 2;for (long long i = 3; i * i <= x; i += 2) {if (x % i == 0) {divs[cnt++] = i;while (x % i == 0) x /= i;}}if (x > 1) divs[cnt++] = x;for (int g = 2;; g++) {bool ok = true;for (int i = 0; i < cnt; i++) {if (modpow(g, (mod - 1) / divs[i], mod) == 1) {ok = false;break;}}if (ok) return g;}}int get_fft_size(int N, int M) {int size_a = 1, size_b = 1;while (size_a < N) size_a <<= 1;while (size_b < M) size_b <<= 1;return max(size_a, size_b) << 1;}// number-theoretic transformtemplate<class mint> void trans(vector<mint> &v, bool inv = false) {if (v.empty()) return;int N = (int)v.size();int MOD = v[0].getmod();int PR = calc_primitive_root(MOD);static bool first = true;static vector<long long> vbw(30), vibw(30);if (first) {first = false;for (int k = 0; k < 30; ++k) {vbw[k] = modpow(PR, (MOD - 1) >> (k + 1), MOD);vibw[k] = modinv(vbw[k], MOD);}}for (int i = 0, j = 1; j < N - 1; j++) {for (int k = N >> 1; k > (i ^= k); k >>= 1);if (i > j) swap(v[i], v[j]);}for (int k = 0, t = 2; t <= N; ++k, t <<= 1) {long long bw = vbw[k];if (inv) bw = vibw[k];for (int i = 0; i < N; i += t) {mint w = 1;for (int j = 0; j < t/2; ++j) {int j1 = i + j, j2 = i + j + t/2;mint c1 = v[j1], c2 = v[j2] * w;v[j1] = c1 + c2;v[j2] = c1 - c2;w *= bw;}}}if (inv) {long long invN = modinv(N, MOD);for (int i = 0; i < N; ++i) v[i] = v[i] * invN;}}// for garnerstatic constexpr int MOD0 = 754974721;static constexpr int MOD1 = 167772161;static constexpr int MOD2 = 469762049;using mint0 = Fp<MOD0>;using mint1 = Fp<MOD1>;using mint2 = Fp<MOD2>;static const mint1 imod0 = 95869806; // modinv(MOD0, MOD1);static const mint2 imod1 = 104391568; // modinv(MOD1, MOD2);static const mint2 imod01 = 187290749; // imod1 / MOD0;// small case (T = mint, long long)template<class T> vector<T> naive_mul(const vector<T> &A, const vector<T> &B) {if (A.empty() || B.empty()) return {};int N = (int)A.size(), M = (int)B.size();vector<T> res(N + M - 1);for (int i = 0; i < N; ++i)for (int j = 0; j < M; ++j)res[i + j] += A[i] * B[j];return res;}// minttemplate<class mint> vector<mint> mul(const vector<mint> &A, const vector<mint> &B) {if (A.empty() || B.empty()) return {};int N = (int)A.size(), M = (int)B.size();if (min(N, M) < 30) return naive_mul(A, B);int MOD = A[0].getmod();int size_fft = get_fft_size(N, M);if (MOD == 998244353) {vector<mint> a(size_fft), b(size_fft), c(size_fft);for (int i = 0; i < N; ++i) a[i] = A[i];for (int i = 0; i < M; ++i) b[i] = B[i];trans(a), trans(b);vector<mint> res(size_fft);for (int i = 0; i < size_fft; ++i) res[i] = a[i] * b[i];trans(res, true);res.resize(N + M - 1);return res;}vector<mint0> a0(size_fft, 0), b0(size_fft, 0), c0(size_fft, 0);vector<mint1> a1(size_fft, 0), b1(size_fft, 0), c1(size_fft, 0);vector<mint2> a2(size_fft, 0), b2(size_fft, 0), c2(size_fft, 0);for (int i = 0; i < N; ++i)a0[i] = A[i].val, a1[i] = A[i].val, a2[i] = A[i].val;for (int i = 0; i < M; ++i)b0[i] = B[i].val, b1[i] = B[i].val, b2[i] = B[i].val;trans(a0), trans(a1), trans(a2), trans(b0), trans(b1), trans(b2);for (int i = 0; i < size_fft; ++i) {c0[i] = a0[i] * b0[i];c1[i] = a1[i] * b1[i];c2[i] = a2[i] * b2[i];}trans(c0, true), trans(c1, true), trans(c2, true);static const mint mod0 = MOD0, mod01 = mod0 * MOD1;vector<mint> res(N + M - 1);for (int i = 0; i < N + M - 1; ++i) {int y0 = c0[i].val;int y1 = (imod0 * (c1[i] - y0)).val;int y2 = (imod01 * (c2[i] - y0) - imod1 * y1).val;res[i] = mod01 * y2 + mod0 * y1 + y0;}return res;}// long longvector<long long> mul_ll(const vector<long long> &A, const vector<long long> &B) {if (A.empty() || B.empty()) return {};int N = (int)A.size(), M = (int)B.size();if (min(N, M) < 30) return naive_mul(A, B);int size_fft = get_fft_size(N, M);vector<mint0> a0(size_fft, 0), b0(size_fft, 0), c0(size_fft, 0);vector<mint1> a1(size_fft, 0), b1(size_fft, 0), c1(size_fft, 0);vector<mint2> a2(size_fft, 0), b2(size_fft, 0), c2(size_fft, 0);for (int i = 0; i < N; ++i)a0[i] = A[i], a1[i] = A[i], a2[i] = A[i];for (int i = 0; i < M; ++i)b0[i] = B[i], b1[i] = B[i], b2[i] = B[i];trans(a0), trans(a1), trans(a2), trans(b0), trans(b1), trans(b2);for (int i = 0; i < size_fft; ++i) {c0[i] = a0[i] * b0[i];c1[i] = a1[i] * b1[i];c2[i] = a2[i] * b2[i];}trans(c0, true), trans(c1, true), trans(c2, true);static const long long mod0 = MOD0, mod01 = mod0 * MOD1;vector<long long> res(N + M - 1);for (int i = 0; i < N + M - 1; ++i) {int y0 = c0[i].val;int y1 = (imod0 * (c1[i] - y0)).val;int y2 = (imod01 * (c2[i] - y0) - imod1 * y1).val;res[i] = mod01 * y2 + mod0 * y1 + y0;}return res;}};// Binomial coefficienttemplate<class T> struct BiCoef {vector<T> fact_, inv_, finv_;constexpr BiCoef() {}constexpr BiCoef(int n) noexcept : fact_(n, 1), inv_(n, 1), finv_(n, 1) {init(n);}constexpr void init(int n) noexcept {fact_.assign(n, 1), inv_.assign(n, 1), finv_.assign(n, 1);int MOD = fact_[0].getmod();for(int i = 2; i < n; i++){fact_[i] = fact_[i-1] * i;inv_[i] = -inv_[MOD%i] * (MOD/i);finv_[i] = finv_[i-1] * inv_[i];}}constexpr T com(int n, int k) const noexcept {if (n < k || n < 0 || k < 0) return 0;return fact_[n] * finv_[k] * finv_[n-k];}constexpr T fact(int n) const noexcept {if (n < 0) return 0;return fact_[n];}constexpr T inv(int n) const noexcept {if (n < 0) return 0;return inv_[n];}constexpr T finv(int n) const noexcept {if (n < 0) return 0;return finv_[n];}};const int MOD = 1e9+7;using mint = Fp<MOD>;template < class T >struct vec : public vector< T > {vec() : vector< T >() {}vec(int n, T e = 0) : vector< T >(n, e) {}vec(initializer_list< T > v) : vector< T >(v) {}int size() const { return vector< T >::size(); }vec& operator+=(const vec& rhs) {assert(size() == rhs.size());rep(i,size()) (*this)[i] += rhs[i];return *this;}vec& operator-=(const vec& rhs) {assert(size() == rhs.size());rep(i,size()) (*this)[i] -= rhs[i];return *this;}vec& operator*=(T x) {rep(i,size()) (*this)[i] *= x;return *this;}vec& operator/=(T x) {x = T(1) / x;rep(i,size()) (*this)[i] *= x;return *this;}vec operator+(const vec& rhs) const { return vec(*this) += rhs; }vec operator-(const vec& rhs) const { return vec(*this) -= rhs; }vec operator*(T x) const { return vec(*this) *= x; }vec operator/(T x) const { return vec(*this) /= x; }bool operator==(const vec& rhs) const {rep(i,size()) if((*this)[i] != rhs[i]) return false;return true;}};template < class T >T dot(const vec< T >& a, const vec< T >& b) {assert(a.size() == b.size());T res(0);rep(i,a.size()) res += a[i] * b[i];return res;}template < class T >struct mat : public vec< vec< T > > {mat(int h, int w, T e = 0) : vec< vec< T > >(h, vec< T >(w, e)) {}mat(initializer_list< initializer_list< T > > m) : vec< vec< T > >(m.size()) {auto it = m.begin();for(int i = 0; it != m.end(); i++, it++) (*this)[i] = vec< T >(*it);}int size() const { return vec< vec< T > >::size(); }mat operator*(const mat &rhs) const {int N = (*this).size(), M = (*this)[0].size(), K = rhs[0].size();assert((*this)[0].size() == rhs.size());mat res(N, K);rep(k,M)rep(i,N)rep(j,K) res[i][j] += (*this)[i][k] * rhs[k][j];return res;}mat& operator*=(const mat &rhs) { return *this = (*this) * rhs; }vec< T > operator*(const vec< T >& rhs) const {assert((*this)[0].size() == rhs.size());vec< T > res(size());rep(i,size()) res[i] = dot((*this)[i], rhs);return res;}vec< T >& operator[](int i) { return vec< vec< T > >::operator[](i); }const vec< T >& operator[](int i) const { return vec< vec< T > >::operator[](i); }mat& operator/=(T x) { rep(i,size()) (*this)[i] /= x; return *this; }mat operator/(T x) const { return (*this) /= x; }bool operator==(const mat& rhs) const {rep(i,size()) if((*this)[i] != rhs[i]) return false;return true;}};template < class T >struct msq : public mat< T > {msq(int n, T e = 0) : mat< T >(n, n, e) {}msq(initializer_list< initializer_list< T > > m) : mat< T >(m) {}msq unit() const {msq I((*this).size());rep(i,(*this).size()) I[i][i] = T(1);return I;}msq pow(ll n) const {msq res = unit(), A = (*this);while(n > 0) {if(n & 1) res *= A;A *= A;n >>= 1;}return res;}T det() const {msq A = *this;T res = 1;rep(i,A.size()) {if(A[i][i] == T(0)) {for(int j = i + 1; j < A.size(); j++) if(A[j][i] != T(0)) {for(int k = i; k < A.size(); k++) swap(A[i][k], A[j][k]);res *= T(-1);break;}}if(A[i][i] == T(0)) return T(0);res *= A[i][i];const T x = T(1) / A[i][i];for(int k = i; k < A.size(); k++) A[i][k] *= x;for(int j = i + 1; j < A.size(); j++) {const T x = A[j][i];for(int k = i; k < A.size(); k++) A[j][k] -= A[i][k] * x;}}return res;}msq inv() const {msq A = *this, B = unit();rep(i,A.size()) {if(A[i][i] == T(0)) {for(int j = i + 1; j < A.size(); j++) if(A[j][i] != T(0)) {for(int k = i; k < A.size(); k++) swap(A[i][k], A[j][k]);for(int k = 0; k < A.size(); k++) swap(B[i][k], B[j][k]);break;}}if(A[i][i] == T(0)) throw "this matrix is not regular.";const T x = T(1) / A[i][i];for(int k = i; k < A.size(); k++) A[i][k] *= x;for(int k = 0; k < A.size(); k++) B[i][k] *= x;for(int j = 0; j < A.size(); j++) if(i != j) {const T x = A[j][i];for(int k = i; k < A.size(); k++) A[j][k] -= A[i][k] * x;for(int k = 0; k < A.size(); k++) B[j][k] -= B[i][k] * x;}}return B;}};int main(){cin.tie(0);ios::sync_with_stdio(0);int N; cin >> N;vector<ll> A(N), B(N);rep(i,N) cin >> A[i];rep(i,N) cin >> B[i];vector<int> I(N);iota(I.begin(), I.end(), 0);sort(I.begin(), I.end(), [&](int i, int j) {return A[i] * (B[j] - 1) < A[j] * (B[i] - 1);});mint ans = 0, x = 1;for(int i : I) {ans += mint(A[i]) * x;x = mint(B[i]) * x;}cout << ans << endl;}