結果

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

ソースコード

diff # 

from _collections import defaultdict
n=int(input())
s=["#"]+list(input())
al=list(".#abcdefghijklmnopqrstuvwxyz")
dic={}
for i in range(28):
    dic[al[i]]=i
dp=[0]*(n+1)*35*35
mod=998244353
def _(i,x,y):
    return i*900+x*29+y

dp[_(0,0,1)]=1
for i in range(n):
    for x in range(28):
        for y in range(28):
            a=al[x]
            b=al[y]
            if s[i+1]!="?":
                if s[i+1]==a or s[i+1]==b:continue
                dp[_(i+1,y,dic[s[i+1]])]+=dp[_(i,x,y)]
                dp[_(i + 1, y, dic[s[i + 1]])]%=mod
            else:
                for z in al:
                    if z=="." or z=="#":continue
                    if z==a or z==b:continue
                    dp[_(i+1,y,dic[z])]+=dp[_(i,x,y)]
                    dp[_(i + 1, y, dic[z])] %=mod





ans=0
for x in range(28):
    for y in range(28):
        ans+=dp[_(n,x,y)]
        ans%=mod
print(ans)
0