結果
問題 | No.856 増える演算 |
ユーザー |
![]() |
提出日時 | 2019-07-26 21:38:09 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 6,254 bytes |
コンパイル時間 | 1,067 ms |
コンパイル使用メモリ | 92,232 KB |
実行使用メモリ | 14,464 KB |
最終ジャッジ日時 | 2024-07-02 06:44:35 |
合計ジャッジ時間 | 5,730 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | WA * 80 |
ソースコード
#ifndef CLASS_POLYNOMIAL #define CLASS_POLYNOMIAL #include <vector> #include <complex> #include <cstdint> #include <algorithm> class polynomial { private: using type = double; const type epsilon = 1.0e-9; std::size_t sz; std::vector<type> a; inline bool equivalent(type ra, type rb) const { return (epsilon <= ra - rb && ra - rb <= epsilon); } void discrete_fourier_transform(std::vector<std::complex<type> >& v, bool rev) { std::size_t n = v.size(); const type pi = acos(type(-1)); for (std::size_t i = 0, j = 1; j < n - 1; ++j) { for (std::size_t k = n >> 1; k > (i ^= k); k >>= 1); if (i > j) std::swap(v[i], v[j]); } for (std::size_t b = 1; b < n; b <<= 1) { std::complex<type> wr = std::polar(type(1), (rev ? type(-1) : type(1)) * pi / b); for (std::size_t i = 0; i < n; i += 2 * b) { std::complex<type> w = type(1); for (std::size_t j = 0; j < b; ++j) { std::complex<type> v0 = v[i + j]; std::complex<type> v1 = w * v[i + j + b]; v[i + j] = v0 + v1; v[i + j + b] = v0 - v1; w *= wr; } } } if (!rev) return; for (std::size_t i = 0; i < n; i++) v[i] /= n; } public: explicit polynomial() : sz(1), a(std::vector<type>({ type() })) {}; explicit polynomial(std::size_t sz_) : sz(sz_), a(std::vector<type>(sz_, type())) {}; explicit polynomial(std::vector<type> a_) : sz(a_.size()), a(a_) {}; polynomial& operator=(const polynomial& p) { sz = p.sz; a = p.a; return (*this); } std::size_t size() const { return sz; } std::size_t degree() const { return sz - 1; } type operator[](std::size_t idx) const { return a[idx]; } type& operator[](std::size_t idx) { return a[idx]; } bool operator==(const polynomial& p) const { for (std::size_t i = 0; i < sz || i < p.sz; ++i) { if (!equivalent(i < sz ? a[i] : type(0), i < p.sz ? p.a[i] : type(0))) { return false; } } return true; } bool operator!=(const polynomial& p) const { return !(operator==(p)); } polynomial resize_transform(std::size_t d) const { // Resize polynomial to d: in other words, f(x) := f(x) mod x^d polynomial ans(*this); ans.sz = d; ans.a.resize(d, type(0)); return ans; } polynomial star_transform() const { // f*(x) = x^degree * f(1/x) polynomial ans(*this); reverse(ans.a.begin(), ans.a.end()); return ans; } polynomial inverse(std::size_t d) const { // Find g(x) where g(x) * f(x) = 1 (mod x^d) polynomial ans(std::vector<type>({ type(1) / a[0] })); while (ans.size() < d) { polynomial nxt; nxt = -ans * resize_transform(ans.size() * 2); nxt.a[0] += type(2); nxt *= ans; ans = nxt.resize_transform(ans.size() * 2); } ans = ans.resize_transform(d); return ans; } polynomial& operator+=(const polynomial& p) { sz = std::max(sz, p.sz); a.resize(sz); for (std::size_t i = 0; i < sz; ++i) a[i] += p.a[i]; return (*this); } polynomial& operator-=(const polynomial& p) { sz = std::max(sz, p.sz); a.resize(sz); for (std::size_t i = 0; i < sz; ++i) a[i] -= p.a[i]; return (*this); } polynomial& operator*=(const polynomial& p) { std::size_t n = 2; while (n < sz * 2 || n < p.sz * 2) n <<= 1; std::vector<std::complex<type> > v(n), pv(n); for (std::size_t i = 0; i < sz; ++i) v[i] = a[i]; for (std::size_t i = 0; i < p.sz; ++i) pv[i] = p.a[i]; discrete_fourier_transform(v, false); discrete_fourier_transform(pv, false); for (std::size_t i = 0; i < n; ++i) v[i] *= pv[i]; discrete_fourier_transform(v, true); sz += p.sz - 1; a.resize(sz, type(0)); for (std::size_t i = 0; i < sz; ++i) a[i] = v[i].real(); return (*this); } polynomial operator+() const { return polynomial(*this); } polynomial operator-() const { return polynomial() - polynomial(*this); } polynomial operator+(const polynomial& p) const { return polynomial(*this) += p; } polynomial operator-(const polynomial& p) const { return polynomial(*this) -= p; } polynomial operator*(const polynomial& p) const { return polynomial(*this) *= p; } }; #endif #ifndef CLASS_MODINT #define CLASS_MODINT #include <cstdint> template <std::uint32_t mod> class modint { private: std::uint32_t n; public: modint() : n(0) {}; modint(std::int64_t n_) : n((n_ >= 0 ? n_ : mod - (-n_) % mod) % mod) {}; static constexpr std::uint32_t get_mod() { return mod; } std::uint32_t get() const { return n; } bool operator==(const modint& m) const { return n == m.n; } bool operator!=(const modint& m) const { return n != m.n; } modint& operator+=(const modint& m) { n += m.n; n = (n < mod ? n : n - mod); return *this; } modint& operator-=(const modint& m) { n += mod - m.n; n = (n < mod ? n : n - mod); return *this; } modint& operator*=(const modint& m) { n = std::uint64_t(n) * m.n % mod; return *this; } modint operator+(const modint& m) const { return modint(*this) += m; } modint operator-(const modint& m) const { return modint(*this) -= m; } modint operator*(const modint& m) const { return modint(*this) *= m; } modint inv() const { return (*this).pow(mod - 2); } modint pow(std::uint64_t b) const { modint ans = 1, m = modint(*this); while (b) { if (b & 1) ans *= m; m *= m; b >>= 1; } return ans; } }; #endif // CLASS_MODINT #include <vector> #include <iostream> using namespace std; using modulo = modint<1000000007>; int main() { cin.tie(0); ios_base::sync_with_stdio(false); int N; cin >> N; vector<int> A(N); for (int i = 0; i < N; ++i) cin >> A[i]; int mx = *max_element(A.begin(), A.end()); polynomial hist(mx + 1); for (int i = 0; i < N; ++i) hist[A[i]] += 1.0; hist *= hist; for (int i = 0; i < N; ++i) hist[A[i] * 2] -= 1.0; for (int i = 0; i <= 2 * mx; ++i) hist[i] *= 0.5; modulo ans = 1; for (int i = 0; i <= 2 * mx; ++i) { if (hist[i] > 0) { ans *= modulo(i).pow(hist[i]); } } long long sum = 0; for (int i = N - 1; i >= 0; --i) { ans *= modulo(A[i]).pow(sum); sum += A[i]; } int curmin = 1 << 30, p1 = -1, p2 = -1; double curlog = 1.0e+99; for (int i = N - 1; i >= 0; --i) { double newlog = log(A[i]) * curmin; if (curlog > newlog) { curlog = newlog; p1 = A[i]; p2 = curmin; } curmin = min(curmin, A[i]); } ans *= modulo(p1 + p2).inv() * modulo(p1).pow(p2).inv(); cout << ans.get() << endl; return 0; }