結果

問題 No.1492 01文字列と転倒
ユーザー LyricalMaestro
提出日時 2025-07-22 00:46:52
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 1,884 ms / 4,000 ms
コード長 1,214 bytes
コンパイル時間 282 ms
コンパイル使用メモリ 82,668 KB
実行使用メモリ 273,516 KB
最終ジャッジ日時 2025-07-22 00:47:12
合計ジャッジ時間 16,983 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 22
権限があれば一括ダウンロードができます

ソースコード

diff # 

##https://yukicoder.me/problems/no/1492


def main():
    N, M = map(int, input().split())

    dp = [ {} for _ in range(1)]
    dp[0][0] = 1

    for n in range(2 * N):
        min_n = min(n + 1, N)
        new_dp = [{} for _ in range(min_n + 1)]

        for k in range(len(dp)):
            dp0 = dp[k]
            # 1を足す
            x = n - k
            if k > x:
                new_dp0 = new_dp[k]
                for key, value in dp0.items():
                    if key not in new_dp0:
                        new_dp0[key] = 0
                    new_dp0[key] += value
                    new_dp0[key] %= M
            
            # 0を足す
            o = n - k
            if k + 1 <= min_n:
                new_dp0 = new_dp[k + 1]
                for key, value in dp0.items():
                    new_key = key + o
                    if new_key not in new_dp0:
                        new_dp0[new_key] = 0
                    new_dp0[new_key] += value
                    new_dp0[new_key] %= M
        
        dp = new_dp

    for k in range(N ** 2 + 1):
        if k not in dp[-1]:
            print(0)
        else:
            print(dp[-1][k])





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