結果

問題 No.1492 01文字列と転倒
コンテスト
ユーザー lam6er
提出日時 2025-03-20 18:54:26
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 1,255 bytes
コンパイル時間 173 ms
コンパイル使用メモリ 82,532 KB
実行使用メモリ 282,932 KB
最終ジャッジ日時 2025-03-20 18:56:51
合計ジャッジ時間 6,529 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 17 TLE * 5
権限があれば一括ダウンロードができます

ソースコード

diff # 

from collections import defaultdict

def main():
    import sys
    input = sys.stdin.read().split()
    N = int(input[0])
    M = int(input[1])
    
    current = defaultdict(lambda: defaultdict(int))
    current[0][0] = 1  # Initial state: length 0, balance 0, inversion count 0
    
    for step in range(2 * N):
        next_step = defaultdict(lambda: defaultdict(int))
        for o in current:
            ks = current[o]
            for k in ks:
                cnt = ks[k]
                # Option 1: Add '0'
                new_o = o + 1
                delta = (step - o) // 2
                new_k = k + delta
                next_step[new_o][new_k] = (next_step[new_o][new_k] + cnt) % M
                # Option 2: Add '1' if possible
                if o > 0:
                    new_o2 = o - 1
                    new_k2 = k
                    next_step[new_o2][new_k2] = (next_step[new_o2][new_k2] + cnt) % M
        current = next_step
    
    # Collect results for balance 0
    max_k = N * N
    result = [0] * (max_k + 1)
    if 0 in current:
        for k in current[0]:
            if k <= max_k:
                result[k] = current[0][k] % M
    
    for val in result:
        print(val % M)

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