結果

問題 No.1646 Avoid Palindrome
コンテスト
ユーザー 👑 Kazun
提出日時 2021-08-13 22:10:14
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 1,342 bytes
コンパイル時間 344 ms
コンパイル使用メモリ 82,240 KB
実行使用メモリ 77,848 KB
最終ジャッジ日時 2024-10-03 19:19:28
合計ジャッジ時間 5,118 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other TLE * 1 -- * 39
権限があれば一括ダウンロードができます

ソースコード

diff # 

from string import ascii_lowercase as X
from collections import defaultdict
N=int(input())
S=["*"]+list(input())
Mod=998244353

#==================================================
def answer(x):
    exit(print(x))

#==================================================
if N==1:
    if S[1]=="?":
        answer(26)
    else:
        answer(1)

for i in range(1,N):
    if S[i]==S[i+1] and S[i]!="?":
        answer(0)

for i in range(1,N-1):
    if S[i]==S[i+2] and S[i]!="?":
        answer(0)

D=defaultdict(int)
if S[1]=="?":
    if S[2]=="?":
        for a in X:
            for b in X:
                if a!=b:
                    D[(a,b)]=1
    else:
        for a in X:
            if a!=S[2]:
                D[(a,S[2])]=1
else:
    if S[2]=="?":
        for b in X:
            if S[1]!=b:
                D[(S[1],b)]=1
    else:
        D[(S[1],S[2])]=1

for c in S[3:]:
    E=D
    D=defaultdict(int)

    if c=="?":
        L=defaultdict(int)
        M=defaultdict(int)

        for a,b in E:
            L[b]+=E[(a,b)]
            M[(b,a)]+=E[(a,b)]
            M[(b,b)]+=E[(a,b)]

        for a in X:
            for b in X:
                D[(a,b)]=L[a]-M[(a,b)]
    else:
        for a,b in E:
            if a!=c and b!=c:
                D[(b,c)]+=E[(a,b)]

    for a,b in D:
        D[(a,b)]%=Mod

print(sum(D.values())%Mod)
0