結果
問題 |
No.1084 積の積
|
ユーザー |
![]() |
提出日時 | 2020-06-20 13:48:45 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 67 ms / 2,000 ms |
コード長 | 2,430 bytes |
コンパイル時間 | 2,001 ms |
コンパイル使用メモリ | 180,088 KB |
実行使用メモリ | 6,944 KB |
最終ジャッジ日時 | 2024-07-03 17:14:39 |
合計ジャッジ時間 | 4,015 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 5 |
other | AC * 27 |
ソースコード
#pragma GCC optimize("O3") #include <bits/stdc++.h> #define ll long long #define rep(i,n) for(ll i=0;i<(n);i++) #define pll pair<ll,ll> #define pq priority_queue #define pb push_back #define eb emplace_back #define fi first #define se second #define ios ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0); #define lb(c,x) distance(c.begin(),lower_bound(all(c),x)) #define ub(c,x) distance(c.begin(),upper_bound(all(c),x)) using namespace std; template<class T> inline bool chmax(T& a,T b){if(a<b){a=b;return 1;}return 0;} template<class T> inline bool chmin(T& a,T b){if(a>b){a=b;return 1;}return 0;} const ll mod=1e9+7; struct mint { ll x; mint(ll x=0):x((x%mod+mod)%mod){} //コンストラクタを呼んで自動的にmodを取っている。 mint operator-() const { return mint(-x);} mint& operator+=(const mint a) { if ((x += a.x) >= mod) x -= mod; //メンバ関数にはthisポインタがある。メンバ変数の値を返す。 return *this; } mint& operator-=(const mint a) { if ((x += mod-a.x) >= mod) x -= mod; return *this; } mint& operator*=(const mint a) { (x *= a.x) %= mod; return *this; } mint operator+(const mint a) const { mint res(*this); return res+=a; } mint operator-(const mint a) const { mint res(*this); return res-=a; } mint operator*(const mint a) const { mint res(*this); return res*=a; } mint pow(ll t) const { if (!t) return 1; mint a = pow(t>>1); //a=x/2 a *= a; //繰り返し二乗法 if (t&1) a *= *this; //tが奇数のときはxを1回かける return a; } // for prime mod mint inv() const { return pow(mod-2); } mint& operator/=(const mint a) { return (*this) *= a.inv(); } mint operator/(const mint a) const { mint res(*this); return res/=a; } }; int main(){ ll n; cin >> n; vector<ll> a(n),x(n); rep(i,n){ cin >> a[i]; if(a[i]==0){ cout << 0 << endl; return 0; } } ll le=0,ri=0; ll v=1; mint ans=1; mint rui=1; for(ll i=0;i<n;i++){ le=i; if(ri<i){ ri=i; } while(ri<=n-1 && v*a[ri]<1000000000){ v*=a[ri]; rui*=v; ri++; } ans*=rui; v/=a[le]; mint dv=a[le]; rui/=dv.pow(ri-le); } cout << ans.x << endl; }