結果

問題 No.856 増える演算
ユーザー lam6er
提出日時 2025-03-31 17:43:23
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 3,333 bytes
コンパイル時間 149 ms
コンパイル使用メモリ 82,800 KB
実行使用メモリ 73,204 KB
最終ジャッジ日時 2025-03-31 17:44:48
合計ジャッジ時間 32,650 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 37 WA * 12 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 min_val
    X = min(A)
    countX = A.count(X)
    candidates = []
    
    if countX >= 2:
        min_val = (2 * X) * pow(X, X, MOD) % MOD
    else:
        # Need to find Y which is the next minimum
        min_val_xy = None
        Y_list = sorted(set(A))
        Y_idx = Y_list.index(X) + 1
        if Y_idx >= len(Y_list):
            # Not possible since N >=2 and countX=1
            Y = X
        else:
            Y = Y_list[Y_idx]
        countY = A.count(Y)
        
        # Calculate candidate_xy: (X + Y) * X^Y mod MOD
        candidate_xy = (X + Y) * pow(X, Y, MOD) % MOD
        candidates.append(candidate_xy)
        
        if countY >= 2:
            candidate_yy = (2 * Y) * pow(Y, Y, MOD) % MOD
            candidates.append(candidate_yy)
        
        # Also consider cases where other pairs might be smaller, but unlikely
        # For safety, check other small values in A (up to first 200 elements)
        sorted_A = sorted(A)
        candidates2 = []
        m = min(200, N)
        for i in range(m):
            for j in range(i+1, m):
                a = sorted_A[i]
                b = sorted_A[j]
                val = (a + b) * pow(a, b, MOD) % MOD
                candidates2.append(val)
        if candidates2:
            min_candidate2 = min(candidates2)
            candidates.append(min_candidate2)
        
        # Also check original array's first few elements for min pairs
        candidates3 = []
        for i in range(min(100, N)):
            for j in range(i+1, min(i+100, N)):
                a = A[i]
                b = A[j]
                val = (a + b) * pow(a, b, MOD) % MOD
                candidates3.append(val)
        if candidates3:
            min_candidate3 = min(candidates3)
            candidates.append(min_candidate3)
        
        min_val = min(candidates)
    
    # Compute product_part2: product Ai^sum_{j>i} Aj mod MOD
    sum_right = [0] * N
    for i in range(N-2, -1, -1):
        sum_right[i] = sum_right[i+1] + A[i+1]
        if sum_right[i] >= MOD-1:
            sum_right[i] %= MOD-1  # Because of Fermat's little theorem
    
    product_part2 = 1
    for i in range(N-1):
        a = A[i]
        exponent = sum_right[i]
        if exponent == 0:
            continue
        if a == 0:
            product_part2 = 0
            break
        a_mod = a % MOD
        product_part2 = product_part2 * pow(a_mod, exponent, MOD) % MOD
    
    # Compute product_part1: product (Ai + Aj) mod MOD for all i < j
    # Impossible to compute for N=1e5; thus this part is omitted and
    # the approach is adjusted to use logarithms and handle dynamically
    product_part1 = 1
    for i in range(N):
        for j in range(i+1, N):
            term = (A[i] + A[j]) % MOD
            product_part1 = product_part1 * term % MOD
    
    total_product = product_part1 * product_part2 % MOD
    
    # Compute inverse of min_val mod 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)
    
    result = total_product * inv_min_val % MOD
    print(result)

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