結果

問題 No.1084 積の積
ユーザー Drice
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff # 

#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;
}
0