結果

問題 No.1510 Simple Integral
コンテスト
ユーザー gew1fw
提出日時 2025-06-12 16:07:22
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 2,134 bytes
コンパイル時間 238 ms
コンパイル使用メモリ 82,192 KB
実行使用メモリ 67,364 KB
最終ジャッジ日時 2025-06-12 16:07:26
合計ジャッジ時間 3,408 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 13 WA * 30
権限があれば一括ダウンロードができます

ソースコード

diff # 

MOD = 998244353

def main():
    import sys
    input = sys.stdin.read().split()
    N = int(input[0])
    A = list(map(int, input[1:N+1]))
    
    # Precompute factorial and inverse factorial up to 200
    max_fact = 200
    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
    
    from collections import defaultdict
    freq = defaultdict(int)
    for a in A:
        freq[a] += 1
    
    result = 0
    for a in freq:
        k = freq[a]
        # Compute pow(2, 2-2k)
        exponent = (2 - 2 * k) % (MOD-1)
        pow_2 = pow(2, exponent, MOD)
        # Compute (2k-2)!
        if 2*k - 2 < 0:
            fact_2k_2 = 1
        else:
            fact_2k_2 = fact[2*k - 2]
        # Compute inv_fact[k-1]^2
        if k-1 < 0:
            inv_k_1 = 1
        else:
            inv_k_1 = inv_fact[k-1]
        inv_k_1_sq = inv_k_1 * inv_k_1 % MOD
        # Compute sign (-1)^(k-1)
        sign = pow(MOD-1, k-1, MOD)
        # Compute numerator_part
        numerator_part = pow_2 * fact_2k_2 % MOD
        numerator_part = numerator_part * inv_k_1_sq % MOD
        numerator_part = numerator_part * sign % MOD
        
        # Compute denominator_part
        a_mod = a % MOD
        a_pow = pow(a_mod, 2*k - 1, MOD)
        product = 1
        for b in freq:
            if b == a:
                continue
            b_mod = b % MOD
            term = (b_mod * b_mod - a_mod * a_mod) % MOD
            term_pow = pow(term, freq[b], MOD)
            product = product * term_pow % MOD
        denominator_part = a_pow * product % MOD
        # Compute inverse denominator
        if denominator_part == 0:
            print(0)
            return
        inv_denominator = pow(denominator_part, MOD-2, MOD)
        # Add to result
        term_a = numerator_part * inv_denominator % MOD
        result = (result + term_a) % MOD
    print(result)

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