結果
| 問題 | No.856 増える演算 |
| ユーザー |
 jell
|
| 提出日時 | 2019-08-01 18:04:29 |
| 言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 98 ms / 3,153 ms |
| コード長 | 14,710 bytes |
| コンパイル時間 | 1,951 ms |
| コンパイル使用メモリ | 142,224 KB |
| 実行使用メモリ | 21,020 KB |
| 最終ジャッジ日時 | 2024-07-05 07:45:53 |
| 合計ジャッジ時間 | 8,179 ms |
|
ジャッジサーバーID （参考情報） |
judge3 / judge5 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 80 |
ソースコード
#ifndef LOCAL#pragma GCC optimize("Ofast")#endif#include <cassert>#include <cstring>#include <iostream>#include <algorithm>#include <functional>#include <queue>#include <deque>#include <stack>#include <list>#include <set>#include <map>#include <unordered_set>#include <unordered_map>#include <complex>#include <iomanip>#include <bitset>#include <random>using namespace std;using i64 = int_fast64_t;using pii = pair<int, int>;using pli = pair<int_fast64_t, int>;using pll = pair<int_fast64_t, int_fast64_t>;template <class T> using heap = priority_queue<T>;template <class T> using minheap = priority_queue<T, vector<T>, greater<T>>;template <class T> constexpr T inf = numeric_limits<T>::max() / (T)2 - (T)123456;constexpr int dx[9] = {1, 0, -1, 0, 1, -1, -1, 1, 0};constexpr int dy[9] = {0, 1, 0, -1, 1, 1, -1, -1, 0};constexpr long double Pi = 3.1415926535897932384626433832;constexpr long double Golden = 1.61803398874989484820;#define iostream_untie true#define stdout_precision 10#define stderr_precision 10#define itrep(i,v) for(auto i = begin(v); i != end(v); ++i)#define ritrep(i,v) for(auto i = rbegin(v); i != rend(v); ++i)#define rep(i,n) for(int_fast64_t i = 0; i < (int_fast64_t)(n); ++i)#define rrep(i,n) for(int_fast64_t i = (int_fast64_t)(n) - 1; i >= 0; --i)#define all(v) begin(v), end(v)#define rall(v) rbegin(v), rend(v)#define fir first#define sec second#define u_map unordered_map#define u_set unordered_set#define l_bnd lower_bound#define u_bnd upper_bound#define emp emplace#define emf emplace_front#define emb emplace_back#define pof pop_front#define pob pop_back#define mkp make_pair#define mkt make_tuple#define popcnt __builtin_popcountnamespace setup {struct setupper {setupper() {if(iostream_untie) {ios::sync_with_stdio(false);std::cin.tie(nullptr);std::cout.tie(nullptr);std::cerr.tie(nullptr);}std::cout << std::fixed << std::setprecision(stdout_precision);std::cerr << std::fixed << std::setprecision(stderr_precision);#ifdef LOCALif(!freopen("stderr.txt","wt",stderr)) {freopen("CON","wt",stderr);std::cerr << "Failed to open the stderr file\n";}if(!freopen("stdout.txt","wt",stdout)) {freopen("CON","wt",stdout);std::cerr << "Failed to open the stdout file\n";}if(!freopen("stdin.txt","rt",stdin)) {freopen("CON","rt",stdin);std::cerr << "Failed to open the stdin file.\n";}// auto print_atexit = []() {// std::cerr << "Exec time : " << clock() / (double)CLOCKS_PER_SEC * 1000.0 << "ms\n";// std::cerr << "------------\n";// };// atexit((void(*)())print_atexit);#endif}} __setupper;}namespace std {template <class RAitr> void rsort(RAitr __first, RAitr __last) {sort(__first, __last, greater<>());}template <class T> void hash_combine(size_t &seed, T const &key) {seed ^= hash<T>()(key) + 0x9e3779b9 + (seed << 6) + (seed >> 2);}template <class T, class U> struct hash<pair<T,U>> {size_t operator()(pair<T,U> const &pr) const{size_t seed = 0;hash_combine(seed,pr.first);hash_combine(seed,pr.second);return seed;}};template <class tuple_t, size_t index = tuple_size<tuple_t>::value - 1>struct hashval_calc {static void apply(size_t& seed, tuple_t const& t) {hashval_calc<tuple_t, index - 1>::apply(seed, t);hash_combine(seed,get<index>(t));}};template <class tuple_t>struct hashval_calc<tuple_t, 0> {static void apply(size_t& seed, tuple_t const& t) {hash_combine(seed,get<0>(t));}};template <class ...T> struct hash<tuple<T...>> {size_t operator()(tuple<T...> const& t) const{size_t seed = 0;hashval_calc<tuple<T...>>::apply(seed,t);return seed;}};}template <class T, class U> istream &operator>> (istream &s, pair<T,U> &p) { return s >> p.first >> p.second; }template <class T, class U> ostream &operator<< (ostream &s, const pair<T,U> p) { return s << p.first << " " << p.second; }template <class T> istream &operator>> (istream &s, vector<T> &v) { for(T &e : v) { s >> e; } return s; }template <class T> ostream &operator<< (ostream &s, const vector<T> &v) {for(size_t i = 0; i < v.size(); ++i) { s << (i ? " " : "") << v[i]; } return s;}template <class tuple_t, size_t index>struct tupleos {static ostream &apply(ostream &s, const tuple_t &t) {tupleos<tuple_t,index - 1>::apply(s,t);return s << " " << get<index>(t);}};template <class tuple_t>struct tupleos<tuple_t, 0> {static ostream &apply(ostream &s, const tuple_t &t) {return s << get<0>(t);}};template <class ...T> ostream &operator<< (ostream &s, const tuple<T...> &t) {return tupleos<tuple<T...>, tuple_size<tuple<T...>>::value - 1>::apply(s,t);}template <> ostream &operator<< (ostream &s, const tuple<> &t) { return s; }#define dump(...) cerr << " [ " << __LINE__ << " : " << __FUNCTION__ << " ] " << #__VA_ARGS__ << " : ";\dump_func(__VA_ARGS__)template <class T> void dump_func(T x) { cerr << x << '\n'; }template <class T,class ...Rest> void dump_func(T x, Rest ... rest) { cerr << x << ","; dump_func(rest...); }template <class T> void write(T x) { cout << x << '\n'; }template <class T, class ...Rest> void write(T x, Rest ... rest) { cout << x << ' '; write(rest...); }void writeln() {}template <class T, class ...Rest> void writeln(T x, Rest ... rest) { cout << x << '\n'; writeln(rest...); }#define esc(...) writeln(__VA_ARGS__), exit(0)template <class P> void read(P __first, P __second) {for(P i = __first; i != __second; ++i) cin >> *i;}namespace updater {template <class T> static void add(T &x, const T &y) { x += y; }template <class T> static void ext_add(T &x, const T &y, size_t w) { x += y * w; }template <class T> static void mul(T &x, const T &y) { x *= y; }template <class T> static void ext_mul(T &x, const T &y, size_t w) { x *= (T)pow(y,w); }template <class T> static bool chmax(T &x, const T &y) { return x < y ? x = y, true : false; }template <class T> static bool chmin(T &x, const T &y) { return x > y ? x = y, true : false; }};using updater::add;using updater::chmax;using updater::chmin;template <class T> constexpr T minf(const T &x, const T &y) { return min(x,y); }template <class T> constexpr T maxf(const T &x, const T &y) { return max(x,y); }constexpr bool bit(i64 n, int e) { return (n >> e) & 1; }constexpr int_fast64_t mask(int_fast64_t n, int e) { return n & ((1 << e) - 1); }constexpr int ilog(int_fast64_t x, int_fast64_t b = 2) { return x ? 1 + ilog(x / b, b) : -1; }int_fast64_t binry(int_fast64_t ok, int_fast64_t ng, const function<bool(int_fast64_t)> &fn) {while (abs(ok - ng) > 1) {int_fast64_t mid = (ok + ng) / 2;(fn(mid) ? ok : ng) = mid;}return ok;}template <class A, size_t N, class T> void init(A (&array)[N], const T &val) { fill((T*)array,(T*)(array + N),val); }template <class T> vector<int> cmprs(const vector<T> &v) {vector<T> tmp = v; vector<int> ret;sort(begin(tmp),end(tmp));tmp.erase(unique(begin(tmp),end(tmp)), end(tmp));for(T i : v) ret.emplace_back(lower_bound(begin(tmp),end(tmp),i) - begin(tmp));return ret;}template <class T> vector<int> cmprs(const T *__first, const T *__last) {return cmprs(vector<T>(__first, __last));}void for_subset(int_fast64_t s, const function<void(int_fast64_t)> &fn) {int_fast64_t tmp = s;do { fn(tmp); } while((--tmp &= s) != s);}/* The main code follows. */template <int32_t mod>struct modint {int x;constexpr modint() : x(0) {}constexpr modint(int_fast64_t y) : x(y >= 0 ? y % mod : (mod - (-y) % mod) % mod) {}constexpr modint &operator+=(const modint &p) {if((x += p.x) >= mod) x -= mod;return *this;}constexpr modint &operator++() { return ++x,*this; }constexpr modint operator++(int) {modint t = *this;return ++x,t;}constexpr modint &operator-=(const modint &p) {if((x += mod - p.x) >= mod) x -= mod;return *this;}constexpr modint &operator--() { return --x, *this; }constexpr modint operator--(int) {modint t = *this;return --x,t;}constexpr modint &operator*=(const modint &p) {x = (int) (1LL * x * p.x % mod);return *this;}constexpr modint &operator/=(const modint &p) {*this *= inverse(p);return *this;}constexpr modint operator-() const { return modint(-x); }constexpr modint operator+(const modint &p) const { return modint(*this) += p; }constexpr modint operator-(const modint &p) const { return modint(*this) -= p; }constexpr modint operator*(const modint &p) const { return modint(*this) *= p; }constexpr modint operator/(const modint &p) const { return modint(*this) /= p; }constexpr bool operator==(const modint &p) const { return x == p.x; }constexpr bool operator!=(const modint &p) const { return x != p.x; }constexpr bool operator!() const { return !x; }// constexpr bool operator>(const modint &p) const { return x > p.x; }// constexpr bool operator<(const modint &p) const { return x < p.x; }// constexpr bool operator>=(const modint &p) const { return x >= p.x; }// constexpr bool operator<=(const modint &p) const { return x <= p.x; }constexpr static modint inverse(const modint &p) {int a = p.x, b = mod, u = 1, v = 0;while(b > 0) {int t = a / b;a -= t * b;a ^= b ^= a ^= b;u -= t * v;u ^= v ^= u ^= v;}return modint(u);}constexpr static modint pow(modint p, int_fast64_t e) {if(!e) return 1;if(e < 0) e = (e % (mod - 1) + mod - 1) % (mod - 1);return pow(p * p, e >> 1) * (e & 1 ? p : 1);}friend ostream &operator<<(ostream &s, const modint &p) { return s << p.x; }friend istream &operator>>(istream &s, modint &p) {uint_fast64_t x;p = modint((s >> x,x));return s;}};namespace FFT {template <class Real>vector<complex<Real>> fft(vector<complex<Real>> x, bool inverse = false) {size_t n = x.size(),mask = n - 1; //"n" must be a power of two.static vector<complex<Real>> tmp;tmp.resize(n);for(size_t i = n >> 1; i; i >>= 1) {Real theta = Pi * 2 * i * (inverse ? -1 : 1) / n;complex<Real> zeta(cos(theta),sin(theta));complex<Real> powzeta = 1;for(size_t j = 0; j < n; j += i) {for(size_t k = 0; k < i; ++k) {tmp[j + k] = x[k + (mask & j << 1)] + powzeta * x[k + (mask & i + (j << 1))];}powzeta *= zeta;}swap(x,tmp);}if(inverse) for(size_t i = 0; i < n; ++i) x[i] /= n;return x;}template <class T>vector<T> conv(const vector<T> &a, const vector<T> &b) {size_t n = 1;while(n + 1 < a.size() + b.size()) n <<= 1;vector<complex<double>> x(n),y(n);for(size_t i = 0; i != a.size(); ++i) x[i].real(a[i]);for(size_t i = 0; i != b.size(); ++i) x[i].imag(b[i]);x = fft(x,false);for(int i = 0; i < n; ++i) {int j = i ? n - i : 0;y[i] = (x[i] + conj(x[j])) * (x[i] - conj(x[j])) * complex<double>(0,-.25);}y = fft(y,true);vector<T> c(n);for(size_t i = 0; i < n; ++i) c[i] = y[i].real();return c;}template <>vector<int_fast64_t> conv(const vector<int_fast64_t> &a, const vector<int_fast64_t> &b) {size_t n = 1;while(n + 1 < a.size() + b.size()) n <<= 1;vector<complex<double>> x(n),y(n);for(size_t i = 0; i != a.size(); ++i) x[i].real(a[i]);for(size_t i = 0; i != b.size(); ++i) x[i].imag(b[i]);x = fft(x,false);for(int i = 0; i < n; ++i) {int j = i ? n - i : 0;y[i] = (x[i] + conj(x[j])) * (x[i] - conj(x[j])) * complex<double>(0,-.25);}y = fft(y,true);vector<int_fast64_t> c(n);for(size_t i = 0; i < n; ++i) c[i] = round(y[i].real());return c;}template <>vector<int> conv(const vector<int> &a, const vector<int> &b) {size_t n = 1;while(n + 1 < a.size() + b.size()) n <<= 1;vector<complex<double>> x(n), y(n);for(size_t i = 0; i != a.size(); ++i) x[i].real(a[i]);for(size_t i = 0; i != b.size(); ++i) x[i].imag(b[i]);x = fft(x,false);for(int i = 0; i < n; ++i) {int j = i ? n - i : 0;y[i] = (x[i] + conj(x[j])) * (x[i] - conj(x[j])) * complex<double>(0,-.25);}y = fft(y,true);vector<int> c(n);for(size_t i = 0; i < n; ++i) c[i] = round(y[i].real());return c;}}using mint=modint<1000000007>;int n;int a[1<<17];void solve() {mint ans=1;for(i64 i=n-1,r=0; i>=0; r+=a[i--]) {ans*=mint::pow(a[i],r);}vector<i64> cnt(100001);for(int i=0; i<n; ++i) {cnt[a[i]]++;}auto ccv=FFT::conv(cnt,cnt);for(int i=0; i<n; ++i) {ccv[a[i]*2]--;}for(int i=0; i<=200000; ++i) {ccv[i]/=2;}for(int i=2; i<=200000; ++i) {ans*=mint::pow(i,ccv[i]);}for(int i=2; i<=10; ++i) {dump(i,ccv[i]);}int *p=min_element(a,a+n);int *l=min_element(a,p);int *r=min_element(p+1,a+n);if(p==l) {dump(*p,*r);ans/=*r+*p;ans/=mint::pow(*p,*r);} else if(p==a+n-1) {ans/=*l+*p;ans/=mint::pow(*l,*p);} else {auto f=[&](double x, double y) -> double {return y*log(x)+log(x+y);};if(f(*l,*p)>f(*p,*r)) {ans/=*r+*p;ans/=mint::pow(*p,*r);} else {ans/=*l+*p;ans/=mint::pow(*l,*p);}}cout<<ans<<endl;}signed main() {cin>>n;rep(i,n) cin>>a[i];solve();}