結果

問題 No.2391 SAN 値チェック
コンテスト
ユーザー qwewe
提出日時 2025-05-14 13:10:11
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 141 ms / 2,000 ms
コード長 3,235 bytes
コンパイル時間 401 ms
コンパイル使用メモリ 82,304 KB
実行使用メモリ 78,720 KB
最終ジャッジ日時 2025-05-14 13:11:33
合計ジャッジ時間 3,673 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 17
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

import sys

# Set a higher recursion depth limit if needed, although this code is iterative.
# sys.setrecursionlimit(200010) 

def solve():
    # Read input N
    N = int(sys.stdin.readline())
    # Define the modulus
    MOD = 998244353

    # Problem constraints state 1 <= N <= 2 * 10^5.
    # The derivation below assumes N >= 1.

    # Precompute factorials and inverse factorials modulo MOD
    # We need factorials up to N.
    MAX_N = N
    fact = [1] * (MAX_N + 1)
    invfact = [1] * (MAX_N + 1)

    # Calculate factorials: fact[i] = i! mod MOD
    for i in range(1, MAX_N + 1):
        fact[i] = (fact[i-1] * i) % MOD

    # Calculate modular inverse of N! using Fermat's Little Theorem.
    # pow(a, MOD-2, MOD) calculates a^(MOD-2) mod MOD, which is a^(-1) mod MOD for prime MOD.
    # We need N! to be non-zero modulo MOD. Since N <= 2 * 10^5 and MOD is ~10^9, N < MOD, so N! is not divisible by MOD.
    invfact[MAX_N] = pow(fact[MAX_N], MOD - 2, MOD) # Using Python's built-in pow for modular exponentiation

    # Calculate inverse factorials iteratively downwards using the relation (k!)^{-1} = ((k+1)!)^(-1) * (k+1)
    # invfact[i] = (i!)^{-1} mod MOD
    for i in range(MAX_N - 1, -1, -1):
        invfact[i] = (invfact[i+1] * (i+1)) % MOD

    # The expected value A is given by A = sum_{i=0}^{N} a_i * e^i.
    # We derived the formula for the coefficients: a_j = ((-1)^(N-j) * j^(N-j) / (N-j)!)
    # We need to compute a_j mod MOD for j = 0, 1, ..., N.

    # Array to store coefficients a_0, ..., a_N
    ans = [0] * (N + 1)
    
    # Calculate coefficients a_j mod MOD
    
    # For j=0: a_0 = ((-1)^(N-0) * 0^(N-0) / (N-0)!) = ((-1)^N * 0^N / N!)
    # Since N >= 1, N > 0, so 0^N = 0. Thus, a_0 = 0.
    ans[0] = 0

    # Calculate a_j for j from 1 to N
    for j in range(1, N + 1):
        
        # Calculate the power term: j^(N-j) mod MOD
        # The exponent N-j is non-negative.
        # Python's built-in `pow(base, exponent, modulus)` handles modular exponentiation efficiently.
        # It correctly handles edge cases:
        # pow(0, 0, MOD) = 1
        # pow(k, 0, MOD) = 1 for k != 0
        # pow(0, k, MOD) = 0 for k > 0
        power_val = pow(j, N - j, MOD) 
        
        # Get the inverse factorial term: ((N-j)!)^{-1} mod MOD
        # The index N-j ranges from N-1 down to 0. All these inverse factorials are precomputed.
        inv_fact_val = invfact[N - j]
        
        # Calculate the magnitude part of a_j: (j^(N-j) * ((N-j)!)^(-1)) mod MOD
        val = (power_val * inv_fact_val) % MOD
        
        # Apply the sign (-1)^(N-j)
        # Check the parity of N-j. If odd, the sign is -1. If even, the sign is +1.
        if (N - j) % 2 == 1: # If N-j is odd
            # Compute -val mod MOD. The result must be in [0, MOD-1].
            # (MOD - val) % MOD ensures this.
            ans[j] = (MOD - val) % MOD 
        else: # If N-j is even
            # The sign is +1, so just take val.
            ans[j] = val

    # Output the results a_0, ..., a_N, each on a new line.
    # Using list comprehension and join for potentially faster I/O.
    output = [str(ans[i]) for i in range(N + 1)]
    print("\n".join(output))

# Run the solver function
solve()
0