結果

問題 No.1646 Avoid Palindrome
コンテスト
ユーザー U S
提出日時 2021-08-14 01:47:23
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 1,677 bytes
コンパイル時間 272 ms
コンパイル使用メモリ 81,880 KB
実行使用メモリ 83,744 KB
最終ジャッジ日時 2024-10-04 04:41:44
合計ジャッジ時間 5,258 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
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()
if n == 1:
    if s == "?":print(26)
    else:print(1)
    exit()
dp = [0]*703
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]*703
    tar = s[i]
    if tar != "?":
        nxt = ord(tar)-ord("a")+1
        for j in range(27,703):
            u,v = (j-1)//26,modf1(j,26)
            if u != nxt and v != nxt:
                now[v*26+nxt] += dp[j]
                now[v*26+nxt] %= mod
    else:
        for j in range(27,703):
            u,v = (j-1)//26,modf1(j,26)
            for k in range(1,27):
                if u != k and v != k:
                    now[v*26+k] += dp[j]
                    now[v*26+k] %= mod

    for j in range(27,703):
        dp[j] = now[j]
print(sum(dp)%mod)
0