結果
問題 |
No.1084 積の積
|
ユーザー |
|
提出日時 | 2021-08-15 00:53:38 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 36 ms / 2,000 ms |
コード長 | 1,371 bytes |
コンパイル時間 | 2,072 ms |
コンパイル使用メモリ | 198,660 KB |
最終ジャッジ日時 | 2025-01-23 22:17:49 |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 5 |
other | AC * 27 |
ソースコード
#include <bits/stdc++.h> using namespace std; const long long int MOD = 1e9 + 7; __int128 mypow(__int128 x,long long int n) { __int128 res = 1; while(n > 0) { if(n%2) { res = ((res%MOD)*(x%MOD)%MOD); res%=MOD; } x = ((x%MOD)*(x%MOD)%MOD); x%=MOD; n/=2; } return res; } int main(void) { cin.tie(0); ios::sync_with_stdio(false); int n,t; vector <pair<int,int>> v; cin >> n; bool flag = true; int cnt = 1; for(int i=0;i<n;i++) { cin >> t; if(t==0) { cout << 0 << '\n'; return 0; } else if(t > 1) { if(flag==false) { v.push_back(make_pair(1,cnt)); flag = true; cnt = 0; } v.push_back(make_pair(t,1)); } else { if(flag) { flag = false; cnt = 0; } cnt++; } } if(!flag) { v.push_back(make_pair(1,cnt)); } long long int res = 1; for(int i=0;i<v.size();i++) { __int128 mul = 1; int cnt = 0; for(int j=i;j<v.size();j++) { mul*=v[j].first; cnt = v[j].second; //cout << (long long int)(mul) << ' ' << i << ' ' << j << '\n'; if(mul >= 1e9) break; if(v[i].first==1) { res = ((res%MOD)*(mypow(mul,cnt*v[i].second)%MOD)%MOD); res%=MOD; } else { res = ((res%MOD)*(mypow(mul,cnt)%MOD)%MOD); res%=MOD; } } } //cout << res << ' ' << (long long int)(mypow(5,100000)) << '\n'; cout << res << '\n'; return 0; }