結果

問題 No.1646 Avoid Palindrome
ユーザー U SU 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
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 58 ms
72,308 KB
testcase_01 AC 56 ms
64,244 KB
testcase_02 AC 58 ms
65,608 KB
testcase_03 AC 68 ms
69,560 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()
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