結果

問題 No.1646 Avoid Palindrome
ユーザー 👑 H20H20
提出日時 2021-08-14 02:16:26
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 1,879 ms / 3,000 ms
コード長 908 bytes
コンパイル時間 463 ms
コンパイル使用メモリ 82,520 KB
実行使用メモリ 444,492 KB
最終ジャッジ日時 2024-04-26 03:41:52
合計ジャッジ時間 54,975 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 47 ms
61,520 KB
testcase_01 AC 48 ms
60,784 KB
testcase_02 AC 43 ms
60,600 KB
testcase_03 AC 49 ms
63,348 KB
testcase_04 AC 1,580 ms
422,856 KB
testcase_05 AC 1,432 ms
423,348 KB
testcase_06 AC 1,613 ms
410,772 KB
testcase_07 AC 1,566 ms
422,884 KB
testcase_08 AC 1,567 ms
426,340 KB
testcase_09 AC 1,591 ms
408,780 KB
testcase_10 AC 1,537 ms
417,260 KB
testcase_11 AC 1,505 ms
408,000 KB
testcase_12 AC 1,607 ms
422,336 KB
testcase_13 AC 1,442 ms
426,464 KB
testcase_14 AC 1,710 ms
416,076 KB
testcase_15 AC 1,731 ms
422,980 KB
testcase_16 AC 1,703 ms
414,352 KB
testcase_17 AC 1,776 ms
428,852 KB
testcase_18 AC 1,715 ms
419,572 KB
testcase_19 AC 1,722 ms
417,824 KB
testcase_20 AC 1,734 ms
420,400 KB
testcase_21 AC 1,764 ms
428,648 KB
testcase_22 AC 1,713 ms
416,720 KB
testcase_23 AC 1,784 ms
430,468 KB
testcase_24 AC 1,855 ms
443,840 KB
testcase_25 AC 1,863 ms
443,932 KB
testcase_26 AC 1,879 ms
443,996 KB
testcase_27 AC 1,854 ms
444,264 KB
testcase_28 AC 1,841 ms
443,716 KB
testcase_29 AC 1,473 ms
444,220 KB
testcase_30 AC 1,489 ms
444,480 KB
testcase_31 AC 1,560 ms
444,240 KB
testcase_32 AC 1,522 ms
443,928 KB
testcase_33 AC 1,480 ms
444,492 KB
testcase_34 AC 1,842 ms
443,808 KB
testcase_35 AC 40 ms
53,164 KB
testcase_36 AC 37 ms
54,004 KB
testcase_37 AC 44 ms
62,176 KB
testcase_38 AC 38 ms
53,140 KB
testcase_39 AC 42 ms
59,924 KB
testcase_40 AC 43 ms
59,760 KB
testcase_41 AC 46 ms
60,988 KB
testcase_42 AC 44 ms
61,392 KB
testcase_43 AC 1,481 ms
444,164 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

N = int(input())
S = input()
mod = 998244353
DP = [[[0] * 26 for _ in range(26)] for _ in range(N+1)]
DP[0][0][0]=1
for n in range(N):
    if S[n]=='?':
        TEMP = [0]*26
        for i in range(26):
            for j in range(26):
                TEMP[j]+=DP[n][j][i]
        for j in range(26):
            for k in range(26):
                if j!=k:
                    DP[n+1][k][j]=(TEMP[j]-DP[n][j][k])%mod
                if j==0 and k==0 and n==0:
                    DP[1][0][0]=1
                if j!=k and k==0 and n==1:
                    DP[n+1][k][j]=TEMP[j]

    else:
        k = ord(S[n])-97
        for i in range(26):
            for j in range(26):
                if (i!=k or n<=1) and (j!=k or n==0):
                    DP[n+1][k][j]=(DP[n+1][k][j]+DP[n][j][i])%mod                    
ans = 0
for i in range(26):
    for j in range(26):
        ans += DP[N][i][j]
print(ans%mod)
0