結果
問題 | No.1084 積の積 |
ユーザー |
|
提出日時 | 2020-06-20 00:09:44 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 153 ms / 2,000 ms |
コード長 | 2,001 bytes |
コンパイル時間 | 1,621 ms |
コンパイル使用メモリ | 173,796 KB |
実行使用メモリ | 6,944 KB |
最終ジャッジ日時 | 2024-07-03 16:16:02 |
合計ジャッジ時間 | 3,764 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 5 |
other | AC * 27 |
ソースコード
#include <bits/stdc++.h>#define rep(i,n) for(int i=0;i<(int)(n);i++)using namespace std;using ll = long long ;using P = pair<int,int> ;using pll = pair<long long,long long>;constexpr ll INF = 1e9;constexpr long long LINF = 1e17;constexpr int MOD = 1000000007;constexpr double PI = 3.14159265358979323846;ll n = 100005;vector<ll> a(n);long long modpow(long long x, long long n) {long long ret = 1;while (n > 0) {if (n & 1) ret = (ret * x) % MOD;x = (x * x) % MOD;n >>= 1;}return ret;}ll dfs(ll l,ll r){if(l==r) return 1;if(l+1==r) return a[l];ll p1 = dfs(l,(l+r)/2);ll p2 = dfs((l+r)/2,r);ll res = (p1 * p2)%MOD;vector<ll> F,L;ll now = 1;ll m = (l+r)/2;while(1){if(m>=r) break;now *= a[m];m ++;if(now < INF) L.push_back(now);else break;}now = 1;m = ((l+r)/2) - 1;while(1){if(m<l) break;now *= a[m];m --;if(now < INF) F.push_back(now);else break;}reverse(F.begin(),F.end());vector<ll> cnt(L.size(),0);rep(i,F.size()){ll left = -1,right = L.size();while(right - left > 1){ll mid = (left + right)/2;if(F[i]*L[mid]<INF) left = mid;else right = mid;}res = (res * modpow(F[i],left+1))%MOD;if(left!=-1) cnt[left] ++;//cout << "left" << left << endl;}ll point = 0;for(ll i=L.size()-1;i>=0;i--){ll now = cnt[i];if(i==L.size()-1) cnt[i] = now + point;else cnt[i] = now + cnt[i+1] + point;point += now;}rep(i,L.size()){res = (res * modpow(a[i+(l+r)/2],cnt[i]))%MOD;}/*rep(i,L.size()){cout << cnt[i] << " " ;}cout << endl;*/return res;}int main(){cin >> n;a.resize(n);rep(i,n) cin >> a[i];cout << dfs(0,n) << endl;return 0;}