結果

問題 No.1646 Avoid Palindrome
コンテスト
ユーザー U S
提出日時 2021-08-14 01:34:12
言語 PyPy3
(7.3.17)
結果
TLE  
実行時間 -
コード長 2,122 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 370 ms
コンパイル使用メモリ 82,332 KB
実行使用メモリ 84,444 KB
最終ジャッジ日時 2024-10-04 03:59:29
合計ジャッジ時間 5,198 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other TLE * 1 -- * 39
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

# 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):
            u,v = (j-1)//26,modf1(j,26)
            #print(u,v)
            for k in range(1,27):
                if u != k and v != k:
                    now[v*26+k] += dp[j]
                # 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