結果

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

ソースコード

diff # 

# import sys
# #sys.setrecursionlimit(1000000)
# input = sys.stdin.readline
def mp():return map(int,input().split())
def lmp():return list(map(int,input().split()))
import math
import bisect
from copy import deepcopy as dc
from itertools import accumulate
from collections import Counter, defaultdict, deque
import itertools
def ceil(U,V):return (U+V-1)//V
def modf1(N,MOD):return (N-1)%MOD+1
inf = int(1e30)
mod = 998244353

n = int(input())
s = input()
alpha = [""]*720
al = {chr(ord("a")+i):i for i in range(26)}
for i in range(26):
    for j in range(26):
        alpha[(i+1)*26+j+1] = chr(ord("a")+i) + chr(ord(("a"))+j)
if n == 1:
    if s == "?":print(26)
    else:print(1)
    exit()
dp = [0]*720
tar = s[:2]
if "?" not in tar:
    a = modf1(ord(tar[0]) - ord("a")+1,26)
    b = modf1(ord(tar[1]) - ord("a")+1,26)
    dp[a*26+b] += 1
elif tar[0] != "?" and tar[1] == "?":
    a = modf1(ord(tar[0]) - ord("a")+1,26)
    for j in range(26):
        if a-1 != j:dp[a*26+j+1] += 1
elif tar[0] == "?" and tar[1] != "?":
    b = modf1(ord(tar[0]) - ord("a")+1,26)
    for i in range(26):
        if b-1 != i:dp[(i+1)*26+b] += 1
else:
    for i in range(26):
        for j in range(26):
            if i != j:dp[(i+1)*26+j+1] += 1
#print(dp)
for i in range(2,n):
    now = [0]*720
    tar = s[i]
    if tar != "?":
        for j in range(27,703):
            if alpha[j][0] != tar and alpha[j][1] != tar:
                a = modf1(al[alpha[j][1]]+1,26)
                b = modf1(al[tar]+1,26)
                now[a*26+b] += dp[j]
    else:
        for j in range(27,703):
            for k in range(26):
                nxt = chr(ord("a")+k)
                if alpha[j][0] != nxt and alpha[j][1] != nxt:
                    a = modf1(al[alpha[j][1]]+1, 26)
                    b = modf1(al[nxt]+1, 26)
                    now[a * 26 + b] += dp[j]
                    #print(a * 26 + b)
    for i in range(27,703):now[i] %= mod
    dp = now
print(sum(dp)%mod)
0