結果

問題 No.856 増える演算
ユーザー gew1fw
提出日時 2025-06-12 19:32:18
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 1,353 bytes
コンパイル時間 185 ms
コンパイル使用メモリ 82,016 KB
実行使用メモリ 72,948 KB
最終ジャッジ日時 2025-06-12 19:32:53
合計ジャッジ時間 31,848 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 38 WA * 11 TLE * 2 -- * 29
権限があれば一括ダウンロードができます

ソースコード

diff # 

MOD = 10**9 + 7

def main():
    import sys
    input = sys.stdin.read().split()
    idx = 0
    N = int(input[idx])
    idx += 1
    A = list(map(int, input[idx:idx+N]))
    idx += N

    # Compute P2
    suffix_sum = [0] * (N + 1)
    for i in range(N-1, -1, -1):
        suffix_sum[i] = (A[i] + suffix_sum[i+1]) % (MOD-1)  # Fermat's little theorem for exponents

    P2 = 1
    for i in range(N):
        base = A[i]
        exponent = suffix_sum[i+1]
        if exponent == 0:
            P2 = (P2 * 1) % MOD
            continue
        # Compute base^exponent mod MOD
        exponent_mod = exponent % (MOD-1) if base != 0 else 0
        power = pow(base, exponent_mod, MOD)
        P2 = (P2 * power) % MOD

    # Find min_val
    min_val = float('inf')
    min_i = A.index(min(A))
    for j in range(min_i + 1, N):
        a_i = A[min_i]
        a_j = A[j]
        term = (a_i + a_j) * (pow(a_i, a_j, MOD))
        term %= MOD
        if term < min_val:
            min_val = term

    # Compute P1
    P1 = 1
    for i in range(N):
        for j in range(i + 1, N):
            s = (A[i] + A[j]) % MOD
            P1 = (P1 * s) % MOD

    # Compute M
    if min_val == 0:
        print(0)
        return
    M = (P1 * P2) % MOD
    M = (M * pow(min_val, MOD-2, MOD)) % MOD  # Modular inverse

    print(M)

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