結果

問題 No.1084 積の積
ユーザー Drice
提出日時 2020-06-19 23:28:36
言語 C++14
(gcc 13.3.0 + boost 1.87.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
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4 -- * 1
other TLE * 1 -- * 26
権限があれば一括ダウンロードができます

ソースコード

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