結果

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

ソースコード

diff # 

MOD = 10**9 + 7

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    N = int(data[0])
    A = list(map(int, data[1:N+1]))
    
    if N < 2:
        print(1)
        return
    
    # Find the two smallest elements
    s = min(A)
    A_copy = A.copy()
    A_copy.remove(s)
    if not A_copy:
        t = s
    else:
        t = min(A_copy)
    
    # Compute min_term = (s + t) * s^t
    min_sum = s + t
    min_product = pow(s, t, MOD)
    min_term = (min_sum % MOD) * (min_product % MOD) % MOD
    
    # Compute P2: product of A_i^(sum of A_j where j >i)
    suffix_sum = [0] * (N + 1)
    for i in range(N-1, -1, -1):
        suffix_sum[i] = (A[i] + suffix_sum[i+1]) % (MOD-1)
    
    P2 = 1
    for i in range(N):
        a = A[i] % MOD
        exp = suffix_sum[i+1] % (MOD-1)
        if exp == 0 and a == 0:
            P2 = 0
            break
        if a == 0:
            term = 0
        else:
            term = pow(a, exp, MOD)
        P2 = (P2 * term) % MOD
    
    # Compute P1: product of (A_i + A_j) for i < j
    P1 = 1
    for i in range(N):
        for j in range(i+1, N):
            term = (A[i] + A[j]) % MOD
            P1 = (P1 * term) % MOD
    
    # Compute M = (P1 * P2) / min_term mod MOD
    # Since MOD is prime, compute inverse of min_term modulo MOD
    if min_term == 0:
        print(0)
        return
    
    inv_min = pow(min_term, MOD-2, MOD)
    numerator = (P1 * P2) % MOD
    M = (numerator * inv_min) % MOD
    print(M)

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