結果
問題 | No.1084 積の積 |
ユーザー |
![]() |
提出日時 | 2020-08-12 16:28:01 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 80 ms / 2,000 ms |
コード長 | 1,919 bytes |
コンパイル時間 | 1,957 ms |
コンパイル使用メモリ | 116,740 KB |
最終ジャッジ日時 | 2025-01-12 21:27:02 |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 5 |
other | AC * 27 |
コンパイルメッセージ
main.cpp: In function ‘int main(int, const char**)’: main.cpp:44:26: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 44 | vll a(n);re(i, n) scanf("%lld", &a[i]); | ~~~~~^~~~~~~~~~~~~~~
ソースコード
#include <iostream>#include <string>#include <vector>#include <queue>#include <deque>#include <algorithm>#include <set>#include <map>#include <bitset>#include <cmath>#include <functional>#include <iomanip>#define vll vector<ll>#define vvvl vector<vvl>#define vvl vector<vector<ll>>#define VV(a, b, c, d) vector<vector<d>>(a, vector<d>(b, c))#define VVV(a, b, c, d) vector<vvl>(a, vvl(b, vll (c, d)));#define re(c, b) for(ll c=0;c<b;c++)#define all(obj) (obj).begin(), (obj).end()typedef long long int ll;typedef long double ld;using namespace std;ll mpow(ll a, ll b, ll p = -1){ll ret = 1, num = a;if(b==0) return 1;if(p==-1){while(b>0){if(b%2) ret *= num;num = num * num;b /= 2;}}else{while(b>0){if(b%2) ret = (ret*num)%p;num = (num*num)%p;b /= 2;}}return ret;}int main(int argc, char const *argv[]) {ll n;std::cin >> n;vll a(n);re(i, n) scanf("%lld", &a[i]);vll two, zero;for(int i=0;i<n;i++){if(a[i]>1) two.push_back(i);if(a[i]==0) {zero.push_back(i);std::cout << 0 << '\n';return 0;}}two.push_back(n);zero.push_back(n);ll P = 1000000007;ll ans = 1;for(int l=0;l<n;l++){ll t = 1;ll idx = l;for(int i=0;i<32;i++){auto X = lower_bound(all(two), idx);auto Y = lower_bound(all(zero), idx);if((*X)==n&&(*Y)==n){//残り全部1ll one = n - idx;ans = (ans * mpow(t, one, P))%P;break;}if(*Y<*X){//1の連続に0ll one = (*Y) - idx;ans = (ans * mpow(t, one, P))%P;break;}else{//1の連続に2以上ll one = (*X) - idx;ans = (ans * mpow(t, one, P))%P;if(t* a[(*X)]>=1000000000) break;t *= a[*X];ans = (ans * t)%P;idx = (*X) + 1;}}}std::cout << ans << '\n';return 0;}