結果

問題 No.856 増える演算
ユーザー lam6er
提出日時 2025-03-26 15:51:24
言語 PyPy3
(7.3.15)
結果
RE  
実行時間 -
コード長 2,108 bytes
コンパイル時間 308 ms
コンパイル使用メモリ 82,780 KB
実行使用メモリ 84,732 KB
最終ジャッジ日時 2025-03-26 15:52:40
合計ジャッジ時間 10,530 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 8 WA * 6 RE * 6 TLE * 2 -- * 58
権限があれば一括ダウンロードができます

ソースコード

diff # 

MOD = 10**9 + 7

def mod_pow(a, b, mod):
    a %= mod
    result = 1
    while b > 0:
        if b % 2 == 1:
            result = (result * a) % mod
        a = (a * a) % mod
        b //= 2
    return result

def main():
    import sys
    input = sys.stdin.read().split()
    N = int(input[0])
    A = list(map(int, input[1:N+1]))
    
    # Compute product2: product of A_i^sum_{j>i} A_j mod MOD
    sum_j = [0] * (N + 1)
    for i in range(N-1, -1, -1):
        sum_j[i] = (sum_j[i+1] + A[i]) % (MOD-1)  # Using MOD-1 for Fermat's little theorem
    
    product2 = 1
    for i in range(N):
        s = sum_j[i+1]
        if s == 0:
            continue
        a = A[i]
        product2 = (product2 * mod_pow(a, s, MOD)) % MOD
    
    # Find the minimum term
    # Sort the array and check first 200 elements
    sorted_A = sorted(A)
    min_term = None
    K = 200
    for i in range(min(K, len(sorted_A))):
        for j in range(i+1, min(i+1 + K, len(sorted_A))):
            a = sorted_A[i]
            b = sorted_A[j]
            term = (a + b) * mod_pow(a, b, MOD)
            if min_term is None or term < min_term:
                min_term = term
    
    original_A = A
    for i in range(len(original_A)):
        for j in range(i+1, len(original_A)):
            a = original_A[i]
            b = original_A[j]
            term = (a + b) * mod_pow(a, b, MOD)
            if term == min_term:
                min_val = term
                break
        else:
            continue
        break
    
    min_val_mod = min_val % MOD
    denominator = min_val_mod
    
    # Compute product1 and product2 combined
    product_total = 1
    for i in range(len(original_A)):
        a = original_A[i]
        for j in range(i+1, len(original_A)):
            b = original_A[j]
            term = ((a + b) * mod_pow(a, b, MOD)) % MOD
            product_total = (product_total * term) % MOD
    
    # Compute inverse of denominator
    inv_denominator = mod_pow(denominator, MOD-2, MOD)
    result = (product_total * inv_denominator) % MOD
    print(result)

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