結果

問題 No.2219 Re:010
コンテスト
ユーザー lam6er
提出日時 2025-03-31 17:32:43
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 64 ms / 2,000 ms
コード長 1,154 bytes
コンパイル時間 185 ms
コンパイル使用メモリ 82,388 KB
実行使用メモリ 75,976 KB
最終ジャッジ日時 2025-03-31 17:33:39
合計ジャッジ時間 2,372 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 21
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

MOD = 998244353

s = input().strip()

dp0 = 1  # State 0: No part of '010' formed
dp1 = 0  # State 1: First '0' formed
dp2 = 0  # State 2: '0' followed by '1' formed
dp3 = 0  # State 3: '010' fully formed

for c in s:
    if c == '0':
        # Transition for '0'
        nd0 = dp0
        nd1 = (dp1 + dp0) % MOD
        nd2 = dp2
        nd3 = (dp3 + dp2) % MOD
    elif c == '1':
        # Transition for '1'
        nd0 = dp0
        nd1 = dp1
        nd2 = (dp2 + dp1) % MOD
        nd3 = dp3
    else:
        # Transition for '?' considering both '0' and '1'
        # Case when '?' is treated as '0'
        nd0_0 = dp0
        nd1_0 = (dp1 + dp0) % MOD
        nd2_0 = dp2
        nd3_0 = (dp3 + dp2) % MOD
        # Case when '?' is treated as '1'
        nd0_1 = dp0
        nd1_1 = dp1
        nd2_1 = (dp2 + dp1) % MOD
        nd3_1 = dp3
        # Combine both cases
        nd0 = (nd0_0 + nd0_1) % MOD
        nd1 = (nd1_0 + nd1_1) % MOD
        nd2 = (nd2_0 + nd2_1) % MOD
        nd3 = (nd3_0 + nd3_1) % MOD
    
    # Update states for next iteration
    dp0, dp1, dp2, dp3 = nd0 % MOD, nd1 % MOD, nd2 % MOD, nd3 % MOD

print(dp3 % MOD)
0