結果
| 問題 | No.1084 積の積 |
| ユーザー |
 ei1333333
|
| 提出日時 | 2020-06-19 22:30:56 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 85 ms / 2,000 ms |
| コード長 | 6,637 bytes |
| コンパイル時間 | 2,624 ms |
| コンパイル使用メモリ | 203,504 KB |
| 最終ジャッジ日時 | 2025-01-11 07:05:27 |
|
ジャッジサーバーID （参考情報） |
judge5 / judge1 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 5 |
| other | AC * 27 |
ソースコード
#include <bits/stdc++.h>using namespace std;using int64 = long long;const int mod = (int) (1e9 + 7);//const int mod = 998244353;const int64 infll = (1LL << 60) - 1;const int inf = (1 << 30) - 1;struct IoSetup {IoSetup() {cin.tie(nullptr);ios::sync_with_stdio(false);cout << fixed << setprecision(10);cerr << fixed << setprecision(10);}} iosetup;template< typename T1, typename T2 >ostream &operator<<(ostream &os, const pair< T1, T2 > &p) {os << p.first << " " << p.second;return os;}template< typename T1, typename T2 >istream &operator>>(istream &is, pair< T1, T2 > &p) {is >> p.first >> p.second;return is;}template< typename T >ostream &operator<<(ostream &os, const vector< T > &v) {for(int i = 0; i < (int) v.size(); i++) {os << v[i] << (i + 1 != v.size() ? " " : "");}return os;}template< typename T >istream &operator>>(istream &is, vector< T > &v) {for(T &in : v) is >> in;return is;}template< typename T1, typename T2 >inline bool chmax(T1 &a, T2 b) { return a < b && (a = b, true); }template< typename T1, typename T2 >inline bool chmin(T1 &a, T2 b) { return a > b && (a = b, true); }template< typename T = int64 >vector< T > make_v(size_t a) {return vector< T >(a);}template< typename T, typename... Ts >auto make_v(size_t a, Ts... ts) {return vector< decltype(make_v< T >(ts...)) >(a, make_v< T >(ts...));}template< typename T, typename V >typename enable_if< is_class< T >::value == 0 >::type fill_v(T &t, const V &v) {t = v;}template< typename T, typename V >typename enable_if< is_class< T >::value != 0 >::type fill_v(T &t, const V &v) {for(auto &e : t) fill_v(e, v);}template< typename F >struct FixPoint : F {FixPoint(F &&f) : F(forward< F >(f)) {}template< typename... Args >decltype(auto) operator()(Args &&... args) const {return F::operator()(*this, forward< Args >(args)...);}};template< typename F >inline decltype(auto) MFP(F &&f) {return FixPoint< F >{forward< F >(f)};}template< int mod >struct ModInt {int x;ModInt() : x(0) {}ModInt(int64_t y) : x(y >= 0 ? 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.inverse();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; }ModInt inverse() 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(int64_t n) const {ModInt ret(1), mul(x);while(n > 0) {if(n & 1) ret *= mul;mul *= mul;n >>= 1;}return ret;}friend ostream &operator<<(ostream &os, const ModInt &p) {return os << p.x;}friend istream &operator>>(istream &is, ModInt &a) {int64_t t;is >> t;a = ModInt< mod >(t);return (is);}static int get_mod() { return mod; }};using modint = ModInt< mod >;template< typename Monoid >struct SegmentTree {using F = function< Monoid(Monoid, Monoid) >;int sz;vector< Monoid > seg;const F f;const Monoid M1;SegmentTree(int n, const F f, const Monoid &M1) : f(f), M1(M1) {sz = 1;while(sz < n) sz <<= 1;seg.assign(2 * sz, M1);}void set(int k, const Monoid &x) {seg[k + sz] = x;}void build() {for(int k = sz - 1; k > 0; k--) {seg[k] = f(seg[2 * k + 0], seg[2 * k + 1]);}}void update(int k, const Monoid &x) {k += sz;seg[k] = x;while(k >>= 1) {seg[k] = f(seg[2 * k + 0], seg[2 * k + 1]);}}Monoid query(int a, int b) {Monoid L = M1, R = M1;for(a += sz, b += sz; a < b; a >>= 1, b >>= 1) {if(a & 1) L = f(L, seg[a++]);if(b & 1) R = f(seg[--b], R);}return f(L, R);}Monoid operator[](const int &k) const {return seg[k + sz];}template< typename C >int find_subtree(int a, const C &check, Monoid &M, bool type) {while(a < sz) {Monoid nxt = type ? f(seg[2 * a + type], M) : f(M, seg[2 * a + type]);if(check(nxt)) a = 2 * a + type;else M = nxt, a = 2 * a + 1 - type;}return a - sz;}template< typename C >int find_first(int a, const C &check) {Monoid L = M1;if(a <= 0) {if(check(f(L, seg[1]))) return find_subtree(1, check, L, false);return -1;}int b = sz;for(a += sz, b += sz; a < b; a >>= 1, b >>= 1) {if(a & 1) {Monoid nxt = f(L, seg[a]);if(check(nxt)) return find_subtree(a, check, L, false);L = nxt;++a;}}return -1;}template< typename C >int find_last(int b, const C &check) {Monoid R = M1;if(b >= sz) {if(check(f(seg[1], R))) return find_subtree(1, check, R, true);return -1;}int a = sz;for(b += sz; a < b; a >>= 1, b >>= 1) {if(b & 1) {Monoid nxt = f(seg[--b], R);if(check(nxt)) return find_subtree(b, check, R, true);R = nxt;}}return -1;}};int main() {int N;cin >> N;vector< int > A(N);cin >> A;for(auto &p : A) {if(p == 0) {cout << 0 << "\n";return 0;}}auto f = [](int64 a, int64 b) -> int64 {if(a == inf || b == inf) return inf;if(a * b >= (int) (1e9)) return inf;return a * b;};SegmentTree< int64 > seg(N, f, 1);for(int i = 0; i < N; i++) seg.set(i, A[i]);seg.build();vector< modint > S(N + 1);S[0] = 1;for(int i = 0; i < N; i++) S[i + 1] = S[i] * A[i];vector< modint > V(N + 1);V[0] = 1;for(int i = 1; i <= N; i++) V[i] = V[i - 1] * S[i];modint ret = 1;for(int i = 0; i < N; i++) {int pos = seg.find_first(i, [](int64 a) { return a == inf; });if(pos == -1) pos = N;ret *= V[pos] / V[i];ret /= modint(S[i]).pow(pos - i);}cout << ret << "\n";}