結果

問題 No.1646 Avoid Palindrome
ユーザー KazunKazun
提出日時 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
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 54 ms
73,144 KB
testcase_01 AC 55 ms
65,692 KB
testcase_02 AC 54 ms
64,132 KB
testcase_03 AC 90 ms
77,848 KB
testcase_04 TLE -
testcase_05 -- -
testcase_06 -- -
testcase_07 -- -
testcase_08 -- -
testcase_09 -- -
testcase_10 -- -
testcase_11 -- -
testcase_12 -- -
testcase_13 -- -
testcase_14 -- -
testcase_15 -- -
testcase_16 -- -
testcase_17 -- -
testcase_18 -- -
testcase_19 -- -
testcase_20 -- -
testcase_21 -- -
testcase_22 -- -
testcase_23 -- -
testcase_24 -- -
testcase_25 -- -
testcase_26 -- -
testcase_27 -- -
testcase_28 -- -
testcase_29 -- -
testcase_30 -- -
testcase_31 -- -
testcase_32 -- -
testcase_33 -- -
testcase_34 -- -
testcase_35 -- -
testcase_36 -- -
testcase_37 -- -
testcase_38 -- -
testcase_39 -- -
testcase_40 -- -
testcase_41 -- -
testcase_42 -- -
testcase_43 -- -
権限があれば一括ダウンロードができます

ソースコード

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