結果

問題 No.1357 Nada junior high school entrance examination 3rd day
ユーザー lam6er
提出日時 2025-04-15 22:37:52
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 1,881 bytes
コンパイル時間 459 ms
コンパイル使用メモリ 81,716 KB
実行使用メモリ 76,200 KB
最終ジャッジ日時 2025-04-15 22:38:52
合計ジャッジ時間 4,103 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other TLE * 1 -- * 20
権限があれば一括ダウンロードができます

ソースコード

diff # 

MOD = 998244353

def main():
    import sys
    K = int(sys.stdin.readline())
    max_n = 2 * K + 1
    # Precompute factorial and inverse factorial modulo MOD
    factorial = [1] * (max_n + 1)
    for i in range(1, max_n + 1):
        factorial[i] = factorial[i-1] * i % MOD
    inv_factorial = [1] * (max_n + 1)
    inv_factorial[max_n] = pow(factorial[max_n], MOD-2, MOD)
    for i in range(max_n-1, -1, -1):
        inv_factorial[i] = inv_factorial[i+1] * (i+1) % MOD
    
    # Precompute Bernoulli numbers B_2, B_4, ..., B_{2K}
    bernoulli = [0] * (K + 1)  # bernoulli[0] unused, bernoulli[a] is B_{2a}
    if K >= 1:
        # B_2 = 1/6
        inv6 = pow(6, MOD-2, MOD)
        bernoulli[1] = inv6
    
    for a in range(2, K + 1):
        sum_s = 0
        n = 2 * a + 1
        for k in range(1, a):
            # Compute C(n, 2k)
            c = factorial[n] * inv_factorial[2*k] % MOD
            c = c * inv_factorial[n - 2*k] % MOD
            sum_s = (sum_s + c * bernoulli[k]) % MOD
        # numerator = (2a-1)/2 - sum_s
        numerator = (2 * a - 1) * pow(2, MOD-2, MOD) % MOD
        numerator = (numerator - sum_s) % MOD
        denominator = 2 * a + 1
        inv_denominator = pow(denominator, MOD-2, MOD)
        bernoulli[a] = numerator * inv_denominator % MOD
    
    # Compute the coefficients c_0, c_1, ..., c_{2K}
    result = [0] * (2 * K + 1)
    for a in range(1, K + 1):
        # Compute c_{2a} = (2^{2a-1} * B_{2a} * (-1)^{a+1}) / (2a)!
        pow2 = pow(2, 2*a - 1, MOD)
        sign = 1 if (a + 1) % 2 == 0 else MOD - 1
        term = pow2 * sign % MOD
        term = term * bernoulli[a] % MOD
        term = term * inv_factorial[2*a] % MOD
        result[2*a] = term
    
    # Output the result
    output = []
    for coeff in result:
        output.append(str(coeff))
    print(' '.join(output))

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