結果

問題 No.1646 Avoid Palindrome
ユーザー U SU S
提出日時 2021-08-14 01:34:12
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 2,122 bytes
コンパイル時間 171 ms
コンパイル使用メモリ 82,512 KB
実行使用メモリ 84,976 KB
最終ジャッジ日時 2024-04-14 23:06:39
合計ジャッジ時間 5,014 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 57 ms
73,444 KB
testcase_01 AC 60 ms
68,160 KB
testcase_02 AC 57 ms
66,708 KB
testcase_03 AC 66 ms
70,796 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 # 

# 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