結果
問題 | No.1084 積の積 |
ユーザー | Drice |
提出日時 | 2020-06-20 00:02:48 |
言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 55 ms / 2,000 ms |
コード長 | 2,519 bytes |
コンパイル時間 | 347 ms |
コンパイル使用メモリ | 33,948 KB |
実行使用メモリ | 7,332 KB |
最終ジャッジ日時 | 2023-09-16 16:10:27 |
合計ジャッジ時間 | 2,480 ms |
ジャッジサーバーID (参考情報) |
judge11 / judge13 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
5,244 KB |
testcase_01 | AC | 2 ms
5,284 KB |
testcase_02 | AC | 2 ms
5,244 KB |
testcase_03 | AC | 2 ms
5,160 KB |
testcase_04 | AC | 55 ms
7,316 KB |
testcase_05 | AC | 11 ms
7,124 KB |
testcase_06 | AC | 53 ms
7,268 KB |
testcase_07 | AC | 2 ms
5,236 KB |
testcase_08 | AC | 2 ms
5,244 KB |
testcase_09 | AC | 16 ms
7,112 KB |
testcase_10 | AC | 2 ms
5,116 KB |
testcase_11 | AC | 4 ms
5,376 KB |
testcase_12 | AC | 23 ms
6,172 KB |
testcase_13 | AC | 45 ms
7,004 KB |
testcase_14 | AC | 18 ms
5,916 KB |
testcase_15 | AC | 17 ms
5,848 KB |
testcase_16 | AC | 52 ms
7,332 KB |
testcase_17 | AC | 21 ms
6,128 KB |
testcase_18 | AC | 34 ms
6,636 KB |
testcase_19 | AC | 46 ms
7,104 KB |
testcase_20 | AC | 12 ms
5,620 KB |
testcase_21 | AC | 18 ms
5,920 KB |
testcase_22 | AC | 14 ms
5,764 KB |
testcase_23 | AC | 28 ms
6,392 KB |
testcase_24 | AC | 26 ms
6,288 KB |
testcase_25 | AC | 45 ms
7,092 KB |
testcase_26 | AC | 50 ms
7,252 KB |
testcase_27 | AC | 50 ms
7,268 KB |
testcase_28 | AC | 49 ms
7,324 KB |
testcase_29 | AC | 50 ms
7,272 KB |
testcase_30 | AC | 49 ms
7,308 KB |
testcase_31 | AC | 49 ms
7,308 KB |
ソースコード
#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; }