結果
問題 | No.1492 01文字列と転倒 |
ユーザー |
![]() |
提出日時 | 2025-03-31 17:34:52 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 2,258 ms / 4,000 ms |
コード長 | 1,449 bytes |
コンパイル時間 | 773 ms |
コンパイル使用メモリ | 82,776 KB |
実行使用メモリ | 470,308 KB |
最終ジャッジ日時 | 2025-03-31 17:36:01 |
合計ジャッジ時間 | 19,710 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 22 |
ソースコード
import sys from collections import defaultdict def main(): N, M = map(int, sys.stdin.readline().split()) max_k = N * N # Initialize DP table with defaultdict dp = [[defaultdict(int) for _ in range(N+1)] for __ in range(N+1)] dp[0][0][0] = 1 # Base case for a in range(N + 1): for b in range(a + 1): if a + b > 2 * N: continue # Convert to list to avoid runtime error due to changing size during iteration current_ks = list(dp[a][b].items()) for current_k, count in current_ks: if count == 0: continue # Add '0' if possible if a < N: new_a = a + 1 new_b = b new_k = current_k + b if new_k <= max_k: dp[new_a][new_b][new_k] = (dp[new_a][new_b][new_k] + count) % M # Add '1' if possible if b < N and a >= b + 1: new_a = a new_b = b + 1 new_k = current_k dp[new_a][new_b][new_k] = (dp[new_a][new_b][new_k] + count) % M # Prepare the answer array answer = [0] * (max_k + 1) for k in range(max_k + 1): answer[k] = dp[N][N].get(k, 0) % M # Print each K=0 to N^2 for k_val in answer: print(k_val) if __name__ == "__main__": main()