結果

問題 No.856 増える演算
コンテスト
ユーザー lam6er
提出日時 2025-04-16 16:41:14
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 2,477 bytes
コンパイル時間 352 ms
コンパイル使用メモリ 81,984 KB
実行使用メモリ 88,096 KB
最終ジャッジ日時 2025-04-16 16:42:41
合計ジャッジ時間 35,102 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 40 WA * 9 TLE * 2 -- * 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]))
    
    # Find the minimum value of (a + b) * (a ** b)
    min_val = None
    # Check all pairs where a is the minimum element
    min_a = min(A)
    indices = [i for i, x in enumerate(A) if x == min_a]
    # Check pairs among the minimum elements
    if len(indices) >= 2:
        a = min_a
        b = min_a
        current = (a + b) * pow(a, b, MOD)
        if min_val is None or current < min_val:
            min_val = current
    # Check pairs of min_a with other elements
    for i in indices:
        for j in range(n):
            if j == i:
                continue
            if i < j:
                a, b = A[i], A[j]
            else:
                a, b = A[j], A[i]
            if j < i:
                continue  # Ensure i < j
            current = (a + b) * pow(a, b, MOD)
            if min_val is None or current < min_val:
                min_val = current
    # Also check the first few elements for possible minimum
    for i in range(min(n, 100)):
        for j in range(i+1, min(n, i+100)):
            a, b = A[i], A[j]
            current = (a + b) * pow(a, b, MOD)
            if min_val is None or current < min_val:
                min_val = current
    
    # Compute sum_j for each i (sum of A[j] where j > i)
    sum_j = [0] * n
    current_sum = 0
    for i in reversed(range(n)):
        sum_j[i] = current_sum
        current_sum += A[i]
    
    # Compute Q = product of A_i^sum_j[i] mod MOD
    Q = 1
    for i in range(n):
        a = A[i]
        exponent = sum_j[i]
        if a == 0:
            Q = 0
            break
        if exponent == 0:
            continue
        a_mod = a % MOD
        exp_mod = exponent % (MOD-1)
        Q = (Q * pow(a_mod, exp_mod, MOD)) % MOD
    
    # Compute P = product of (A_i + A_j) for all i < j mod MOD
    P = 1
    for j in range(n):
        for i in range(j):
            term = (A[i] + A[j]) % MOD
            P = (P * term) % MOD
    
    # Compute total = (P * Q) // min_val mod MOD
    # But need to handle division in modular arithmetic
    total = (P * Q) % MOD
    min_val_mod = min_val % MOD
    if min_val_mod == 0:
        print(0)
        return
    # Find the modular inverse of min_val_mod
    inv = pow(min_val_mod, MOD-2, MOD)
    result = (total * inv) % MOD
    print(result)

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