結果

問題 No.1667 Forest
ユーザー lam6er
提出日時 2025-03-20 20:42:10
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 342 ms / 3,000 ms
コード長 1,437 bytes
コンパイル時間 173 ms
コンパイル使用メモリ 82,864 KB
実行使用メモリ 73,764 KB
最終ジャッジ日時 2025-03-20 20:42:14
合計ジャッジ時間 3,390 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 15
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys

def main():
    import sys
    sys.setrecursionlimit(1 << 25)
    N, MOD = map(int, sys.stdin.readline().split())

    # Precompute factorial and inverse factorial modulo MOD
    fact = [1] * (N + 1)
    for i in range(1, N+1):
        fact[i] = fact[i-1] * i % MOD

    inv_fact = [1] * (N + 1)
    inv_fact[N] = pow(fact[N], MOD - 2, MOD)
    for i in range(N-1, -1, -1):
        inv_fact[i] = inv_fact[i+1] * (i+1) % MOD

    # Precompute a_k = k^(k-2) / k! mod MOD
    a = [0] * (N + 1)
    for k in range(1, N+1):
        if k == 1:
            # Handle k=1 as a special case (k-2 = -1, which is MOD-1 under modulo)
            ak = 1
        else:
            ak = pow(k, k-2, MOD)
        a[k] = ak * inv_fact[k] % MOD

    # Initialize DP table
    dp = [[0] * (N + 1) for _ in range(N + 1)]
    dp[0][0] = 1

    # Fill DP table
    for c in range(1, N+1):
        for n in range(1, N+1):
            for k in range(1, n+1):
                prev_c = c - 1
                prev_n = n - k
                if prev_c < 0 or prev_n < 0:
                    continue
                dp[c][n] = (dp[c][n] + dp[prev_c][prev_n] * a[k]) % MOD

    # Compute answers for each M
    for M in range(N):
        c = N - M
        if c < 0 or c > N:
            print(0)
        else:
            res = dp[c][N] * fact[N] % MOD
            res = res * inv_fact[c] % MOD
            print(res)

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