結果

問題 No.856 増える演算
コンテスト
ユーザー gew1fw
提出日時 2025-06-12 14:38:05
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 1,638 bytes
コンパイル時間 304 ms
コンパイル使用メモリ 82,252 KB
実行使用メモリ 84,008 KB
最終ジャッジ日時 2025-06-12 14:38:39
合計ジャッジ時間 31,196 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 36 WA * 13 TLE * 2 -- * 29
権限があれば一括ダウンロードができます

ソースコード

diff # 

MOD = 10**9 + 7

def main():
    import sys
    input = sys.stdin.read().split()
    N = int(input[0])
    A = list(map(int, input[1:N+1]))
    
    # Find the minimum value
    sorted_A = sorted(A)
    min_val = None
    K = 200
    for i in range(min(K, len(sorted_A))):
        for j in range(i + 1, min(K, len(sorted_A))):
            a = sorted_A[i]
            b = sorted_A[j]
            current = (a + b) * pow(a, b, MOD * 1000)  # Use a large mod to avoid overflow
            if min_val is None or current < min_val:
                min_val = current
    
    # Now compute the product_part1 (product of (A_i + A_j) for all i<j)
    product_part1 = 1
    for i in range(N):
        for j in range(i + 1, N):
            product_part1 = product_part1 * (A[i] + A[j]) % MOD
    
    # Compute product_part2 (product of A_i^sum(A_j for j > i))
    sum_suffix = [0] * (N + 1)
    for i in range(N-1, -1, -1):
        sum_suffix[i] = (sum_suffix[i+1] + A[i]) % (MOD-1)
    
    product_part2 = 1
    for i in range(N):
        a = A[i]
        exponent = sum_suffix[i+1]
        if a == 0:
            product_part2 = 0
            break
        if a % MOD == 0:
            product_part2 = 0
            break
        product_part2 = product_part2 * pow(a, exponent, MOD) % MOD
    
    total_product = product_part1 * product_part2 % MOD
    
    # Compute inverse of min_val modulo MOD
    min_val_mod = min_val % MOD
    if min_val_mod == 0:
        print(0)
        return
    inv_min_val = pow(min_val_mod, MOD-2, MOD)
    
    answer = total_product * inv_min_val % MOD
    print(answer)

if __name__ == '__main__':
    main()
0