#1061963 (PyPy3) No.856 増える演算

• 問題: 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

ソースコード

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
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()
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX