結果
問題 | No.1084 積の積 |
ユーザー |
|
提出日時 | 2020-06-20 00:02:48 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 54 ms / 2,000 ms |
コード長 | 2,519 bytes |
コンパイル時間 | 298 ms |
コンパイル使用メモリ | 34,688 KB |
実行使用メモリ | 7,520 KB |
最終ジャッジ日時 | 2024-07-03 16:12:32 |
合計ジャッジ時間 | 2,071 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 5 |
other | AC * 27 |
ソースコード
#include<cstdio> struct Element{ int p; long long value; Element(int p = 0,long long value = 0):p(p), value(value){} }; Element e[100005]; const long long mod = 1e9+7; long long a[100005]; int sum[100005]; long long mul[100005]; long long mMul[100005]; long long power(long long a,long long b){ long long res = 1; while(b){ if(b&1) res = res*a%mod; a = a*a%mod; b /= 2; } return res; } long long inv(long long u){ //if(u==0) printf("haha\n"); return power(u,mod-2); } int isBigger(int l,int r){ int valid = r-(l-1); if(valid>=30) return 1; else{ long long cur = 1; for(int i = l; i <= r; i++){ cur *= e[i].value; if(cur>=1000000000) return 1; } return 0; } } int getUpper(int p,int n){ int l = p, r = n; int res = -1; while(l<=r){ int m = (l+r)/2; if(isBigger(p,m)==0){ res = m; l = m+1; } else r = m-1; } return res; } int main(){ //printf("%lld\n",1<<30); //printf("%lld\n",power(5,99999)*power(2,99999)%mod*10ll%mod); int n; scanf("%d",&n); sum[0] = 0, mul[0] = 1; int cnt0 = 0; for(int i = 1; i <= n; i++){ scanf("%lld",&a[i]); sum[i] = sum[i-1]; if(a[i]==1) sum[i]++; if(a[i]==0) cnt0++; mul[i] = mul[i-1]*a[i]%mod; } mMul[0] = 1; for(int i = 1; i <= n; i++) mMul[i] = mMul[i-1]*mul[i]%mod; if(cnt0!=0) printf("0\n"); else{ int p = 1, size = 0; while(p<=n){ if(a[p]==1) p++; else{ e[++size] = Element(p,a[p]); p++; } } //for(int i = 1; i <= size; i++) printf("%d %lld\n",e[i].p,e[i].value); long long ans = 1; p = 1; for(int i = 1; i <= n; i++){ while(p<=size && e[p].p<i) p++; //printf("p = %d\n",p); int j = -1; if(p==size+1) j = n; else{ int upper = getUpper(p,size); //printf("i = %d, upper = %d\n",i,upper); if(upper==size) j = n; else j = e[upper+1].p-1; } //printf("j = %d\n",j); //printf("i = %d, j = %d\n",i,j); long long cur = mMul[j]*inv(mMul[i-1])%mod; cur = cur*inv(power(mul[i-1],j-i+1))%mod; ans = ans*cur%mod; } printf("%lld\n",ans); } return 0; }