結果

問題 No.1646 Avoid Palindrome
コンテスト
ユーザー gew1fw
提出日時 2025-06-12 21:38:51
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 1,237 bytes
コンパイル時間 333 ms
コンパイル使用メモリ 82,456 KB
実行使用メモリ 55,800 KB
最終ジャッジ日時 2025-06-12 21:43:27
合計ジャッジ時間 3,637 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1 WA * 3
other AC * 2 WA * 38
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
from collections import defaultdict

MOD = 998244353

def main():
    s = sys.stdin.readline().strip()
    n = len(s)
    
    dp_prev = defaultdict(int)
    
    # Initialize for the first character (i=0, 0-based)
    if s[0] == '?':
        for c in 'abcdefghijklmnopqrstuvwxyz':
            dp_prev[(None, c)] = 1
    else:
        dp_prev[(None, s[0])] = 1
    
    for i in range(1, n):
        dp_current = defaultdict(int)
        for (a_prev, b_prev), count in dp_prev.items():
            if s[i] == '?':
                possible_c = 'abcdefghijklmnopqrstuvwxyz'
            else:
                possible_c = [s[i]]
            
            for c in possible_c:
                if i == 1:  # Second character (i=1, 0-based)
                    if c == b_prev:
                        continue
                else:
                    if c == b_prev or c == a_prev:
                        continue
                
                new_state = (b_prev, c)
                dp_current[new_state] = (dp_current[new_state] + count) % MOD
        
        dp_prev = dp_current
        if not dp_prev:
            break
    
    result = sum(dp_prev.values()) % MOD
    print(result)

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