結果

問題 No.1084 積の積
ユーザー DriceDrice
提出日時 2020-06-19 23:28:36
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
TLE  
実行時間 -
コード長 1,607 bytes
コンパイル時間 225 ms
コンパイル使用メモリ 33,920 KB
実行使用メモリ 13,756 KB
最終ジャッジ日時 2024-07-03 15:51:09
合計ジャッジ時間 3,841 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
13,756 KB
testcase_01 AC 2 ms
6,940 KB
testcase_02 AC 2 ms
6,940 KB
testcase_03 AC 2 ms
6,944 KB
testcase_04 TLE -
testcase_05 -- -
testcase_06 -- -
testcase_07 -- -
testcase_08 -- -
testcase_09 -- -
testcase_10 -- -
testcase_11 -- -
testcase_12 -- -
testcase_13 -- -
testcase_14 -- -
testcase_15 -- -
testcase_16 -- -
testcase_17 -- -
testcase_18 -- -
testcase_19 -- -
testcase_20 -- -
testcase_21 -- -
testcase_22 -- -
testcase_23 -- -
testcase_24 -- -
testcase_25 -- -
testcase_26 -- -
testcase_27 -- -
testcase_28 -- -
testcase_29 -- -
testcase_30 -- -
testcase_31 -- -
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<cstdio>
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){ return power(u,mod-2); }

int isBigger(int l,int r){
    int valid = r-(l-1)-(sum[r]-sum[l-1]);
    if(valid>=30) return 1;
    else{
        long long cur = 1;
        for(int i = l; i <= r; i++){
            cur *= a[i];
            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);
    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{
        long long ans = 1;
        for(int i = 1; i <= n; i++){
            int j = getUpper(i,n);
            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;
}
0