結果

問題 No.1084 積の積
ユーザー DriceDrice
提出日時 2020-06-19 23:45:23
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
WA  
実行時間 -
コード長 2,376 bytes
コンパイル時間 231 ms
コンパイル使用メモリ 33,988 KB
実行使用メモリ 7,300 KB
最終ジャッジ日時 2023-09-16 15:59:44
合計ジャッジ時間 2,524 ms
ジャッジサーバーID
（参考情報） 		judge15 / judge12
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 3 ms
5,272 KB
testcase_01 AC 2 ms
5,272 KB
testcase_02 AC 2 ms
5,164 KB
testcase_03 AC 2 ms
5,236 KB
testcase_04 WA -
testcase_05 AC 11 ms
7,192 KB
testcase_06 AC 53 ms
7,288 KB
testcase_07 AC 2 ms
5,180 KB
testcase_08 AC 2 ms
5,208 KB
testcase_09 AC 16 ms
7,056 KB
testcase_10 AC 2 ms
5,236 KB
testcase_11 AC 4 ms
5,388 KB
testcase_12 AC 23 ms
6,060 KB
testcase_13 AC 45 ms
7,044 KB
testcase_14 AC 18 ms
5,904 KB
testcase_15 AC 16 ms
5,848 KB
testcase_16 AC 51 ms
7,248 KB
testcase_17 AC 21 ms
6,060 KB
testcase_18 AC 34 ms
6,560 KB
testcase_19 AC 46 ms
7,040 KB
testcase_20 AC 11 ms
5,672 KB
testcase_21 AC 18 ms
5,964 KB
testcase_22 AC 14 ms
5,752 KB
testcase_23 AC 28 ms
6,332 KB
testcase_24 AC 25 ms
6,284 KB
testcase_25 AC 46 ms
7,052 KB
testcase_26 AC 49 ms
7,196 KB
testcase_27 AC 49 ms
7,252 KB
testcase_28 AC 49 ms
7,296 KB
testcase_29 AC 50 ms
7,264 KB
testcase_30 AC 49 ms
7,300 KB
testcase_31 AC 50 ms
7,252 KB
権限があれば一括ダウンロードができます

ソースコード

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){ 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);
    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("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