#1059587 (PyPy3) No.1193 Penguin Sequence

• 問題: No.1193 Penguin Sequence
• ユーザー: lam6er
• 提出日時: 2025-03-26 15:53:25
• 言語: PyPy3 (7.3.15)
• 結果: AC
• 実行時間: 534 ms / 2,000 ms
• コード長: 2,433 bytes
• コンパイル時間: 445 ms
• コンパイル使用メモリ: 82,400 KB
• 実行使用メモリ: 184,540 KB
• 最終ジャッジ日時: 2025-03-26 15:53:59
• 合計ジャッジ時間: 15,347 ms
• ジャッジサーバーID （参考情報）: judge3 / judge5

ファイルパターン	結果
sample	AC * 3
other	AC * 38

ソースコード

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
MOD = 998244353
def main():
    import sys
    input = sys.stdin.read().split()
    N = int(input[0])
    A = list(map(int, input[1:N+1]))
    
    # Compute inv_count using Fenwick Tree
    sorted_unique = sorted(list(set(A)))
    rank_dict = {v: i+1 for i, v in enumerate(sorted_unique)}
    max_rank = len(sorted_unique)
    
    class FenwickTree:
        def __init__(self, size):
            self.size = size
            self.tree = [0] * (self.size + 2)
        
        def update(self, idx, delta=1):
            while idx <= self.size:
                self.tree[idx] += delta
                idx += idx & -idx
        
        def query(self, idx):
            res = 0
            while idx > 0:
                res += self.tree[idx]
                idx -= idx & -idx
            return res
    
    fen = FenwickTree(max_rank)
    inv_count = 0
    for num in reversed(A):
        r = rank_dict[num]
        inv_count += fen.query(r - 1)
        fen.update(r)
    inv_count %= MOD
    
    # Compute total_pairs
    sorted_A = sorted(A)
    total_pairs = 0
    for x in A:
        cnt = bisect.bisect_left(sorted_A, x)
        total_pairs += cnt
    total_pairs %= MOD
    
    # Compute sum_i and sum_i_sq
    sum_i = N * (N + 1) // 2 % MOD
    sum_i_sq = N * (N + 1) * (2 * N + 1) // 6 % MOD
    
    # Compute S = (sum_i^2 - sum_i_sq) / 2 mod MOD
    S = (sum_i * sum_i - sum_i_sq) % MOD
    S = S * pow(2, MOD-2, MOD) % MOD
    
    # Compute case1 and case2
    inv_N = pow(N, MOD-2, MOD) if N != 0 else 0
    inv_N_sq = inv_N * inv_N % MOD
    case1 = S * inv_N_sq % MOD
    
    inv3 = pow(3, MOD-2, MOD)
    case2 = (N + 1) * inv3 % MOD
    
    # Compute product_C
    max_fact = N
    fact = [1] * (max_fact + 1)
    for i in range(1, max_fact + 1):
        fact[i] = fact[i-1] * i % MOD
    
    inv_fact = [1] * (max_fact + 1)
    inv_fact[max_fact] = pow(fact[max_fact], MOD-2, MOD)
    for i in range(max_fact - 1, -1, -1):
        inv_fact[i] = inv_fact[i+1] * (i+1) % MOD
    
    product_C = 1
    for k in range(1, N+1):
        c = fact[N] * inv_fact[k] % MOD
        c = c * inv_fact[N - k] % MOD
        product_C = product_C * c % MOD
    
    # Compute the final answer
    part1 = case1 * total_pairs % MOD
    part2 = case2 * inv_count % MOD
    total = (part1 + part2) % MOD
    answer = total * product_C % MOD
    
    print(answer)
    
if __name__ == '__main__':
    import bisect
    main()
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX