Submission #55244548

Source Code Expand

from collections import defaultdict

MOD = 998244353

n, k = map(int, input().split())
s = input()

dp = [defaultdict(int) for _ in range(n + 1)]
dp[0][""] = 1
for i in range(n):
    for t, v in dp[i].items():
        for c in "AB":
            if c == 'A' and s[i] == 'B':
                continue
            if c == 'B' and s[i] == 'A':
                continue
            
            u = (t + c)[-k:]
            if len(u) == k and u == u[::-1]:
                continue

            dp[i + 1][u] += v
            dp[i + 1][u] %= MOD

ans = 0
for _, v in dp[n].items():
    ans += v
    ans %= MOD

print(ans)

Submission Info

Submission Time
Task D - Avoid K Palindrome
User TangentDay
Language Python (CPython 3.11.4)
Score 450
Code Size 646 Byte
Status AC
Exec Time 1515 ms
Memory 126868 KiB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 450 / 450
Status
AC × 4
AC × 76
Set Name Test Cases
Sample 00_sample_00.txt, 00_sample_01.txt, 00_sample_02.txt, 00_sample_03.txt
All 00_sample_00.txt, 00_sample_01.txt, 00_sample_02.txt, 00_sample_03.txt, 01_random_04.txt, 01_random_05.txt, 01_random_06.txt, 01_random_07.txt, 01_random_08.txt, 01_random_09.txt, 01_random_10.txt, 01_random_11.txt, 01_random_12.txt, 01_random_13.txt, 01_random_14.txt, 01_random_15.txt, 01_random_16.txt, 01_random_17.txt, 01_random_18.txt, 01_random_19.txt, 01_random_20.txt, 01_random_21.txt, 01_random_22.txt, 01_random_23.txt, 01_random_24.txt, 01_random_25.txt, 01_random_26.txt, 01_random_27.txt, 01_random_28.txt, 01_random_29.txt, 01_random_30.txt, 01_random_31.txt, 01_random_32.txt, 01_random_33.txt, 01_random_34.txt, 01_random_35.txt, 01_random_36.txt, 01_random_37.txt, 01_random_38.txt, 01_random_39.txt, 01_random_40.txt, 01_random_41.txt, 01_random_42.txt, 01_random_43.txt, 01_random_44.txt, 01_random_45.txt, 01_random_46.txt, 01_random_47.txt, 01_random_48.txt, 01_random_49.txt, 01_random_50.txt, 01_random_51.txt, 01_random_52.txt, 01_random_53.txt, 01_random_54.txt, 01_random_55.txt, 01_random_56.txt, 01_random_57.txt, 01_random_58.txt, 01_random_59.txt, 01_random_60.txt, 01_random_61.txt, 01_random_62.txt, 01_random_63.txt, 01_random_64.txt, 01_random_65.txt, 01_random_66.txt, 01_random_67.txt, 01_random_68.txt, 01_random_69.txt, 01_random_70.txt, 01_random_71.txt, 01_random_72.txt, 01_random_73.txt, 01_random_74.txt, 01_random_75.txt
Case Name Status Exec Time Memory
00_sample_00.txt AC 11 ms 9264 KiB
00_sample_01.txt AC 17 ms 9676 KiB
00_sample_02.txt AC 11 ms 9248 KiB
00_sample_03.txt AC 12 ms 9388 KiB
01_random_04.txt AC 1472 ms 126816 KiB
01_random_05.txt AC 718 ms 66628 KiB
01_random_06.txt AC 1447 ms 126836 KiB
01_random_07.txt AC 1453 ms 126812 KiB
01_random_08.txt AC 29 ms 10808 KiB
01_random_09.txt AC 721 ms 66564 KiB
01_random_10.txt AC 12 ms 9284 KiB
01_random_11.txt AC 11 ms 9312 KiB
01_random_12.txt AC 13 ms 9264 KiB
01_random_13.txt AC 76 ms 15544 KiB
01_random_14.txt AC 12 ms 9376 KiB
01_random_15.txt AC 278 ms 31992 KiB
01_random_16.txt AC 47 ms 12020 KiB
01_random_17.txt AC 1490 ms 126256 KiB
01_random_18.txt AC 12 ms 9380 KiB
01_random_19.txt AC 11 ms 9376 KiB
01_random_20.txt AC 12 ms 9280 KiB
01_random_21.txt AC 12 ms 9308 KiB
01_random_22.txt AC 11 ms 9240 KiB
01_random_23.txt AC 13 ms 9460 KiB
01_random_24.txt AC 16 ms 9656 KiB
01_random_25.txt AC 1438 ms 125616 KiB
01_random_26.txt AC 11 ms 9332 KiB
01_random_27.txt AC 12 ms 9360 KiB
01_random_28.txt AC 12 ms 9348 KiB
01_random_29.txt AC 51 ms 12632 KiB
01_random_30.txt AC 12 ms 9296 KiB
01_random_31.txt AC 292 ms 33648 KiB
01_random_32.txt AC 94 ms 15920 KiB
01_random_33.txt AC 1476 ms 126812 KiB
01_random_34.txt AC 12 ms 9364 KiB
01_random_35.txt AC 12 ms 9280 KiB
01_random_36.txt AC 12 ms 9412 KiB
01_random_37.txt AC 21 ms 10212 KiB
01_random_38.txt AC 209 ms 26912 KiB
01_random_39.txt AC 224 ms 27840 KiB
01_random_40.txt AC 177 ms 22868 KiB
01_random_41.txt AC 1491 ms 126744 KiB
01_random_42.txt AC 12 ms 9348 KiB
01_random_43.txt AC 11 ms 9304 KiB
01_random_44.txt AC 12 ms 9344 KiB
01_random_45.txt AC 11 ms 9356 KiB
01_random_46.txt AC 13 ms 9516 KiB
01_random_47.txt AC 51 ms 13076 KiB
01_random_48.txt AC 362 ms 37748 KiB
01_random_49.txt AC 717 ms 66692 KiB
01_random_50.txt AC 11 ms 9284 KiB
01_random_51.txt AC 11 ms 9360 KiB
01_random_52.txt AC 11 ms 9344 KiB
01_random_53.txt AC 12 ms 9360 KiB
01_random_54.txt AC 12 ms 9288 KiB
01_random_55.txt AC 87 ms 16324 KiB
01_random_56.txt AC 30 ms 10860 KiB
01_random_57.txt AC 1504 ms 126844 KiB
01_random_58.txt AC 11 ms 9296 KiB
01_random_59.txt AC 11 ms 9344 KiB
01_random_60.txt AC 12 ms 9336 KiB
01_random_61.txt AC 12 ms 9364 KiB
01_random_62.txt AC 11 ms 9380 KiB
01_random_63.txt AC 53 ms 13144 KiB
01_random_64.txt AC 1515 ms 126868 KiB
01_random_65.txt AC 716 ms 66588 KiB
01_random_66.txt AC 12 ms 9340 KiB
01_random_67.txt AC 11 ms 9300 KiB
01_random_68.txt AC 12 ms 9372 KiB
01_random_69.txt AC 12 ms 9340 KiB
01_random_70.txt AC 12 ms 9336 KiB
01_random_71.txt AC 14 ms 9336 KiB
01_random_72.txt AC 723 ms 66320 KiB
01_random_73.txt AC 720 ms 66132 KiB
01_random_74.txt AC 11 ms 9264 KiB
01_random_75.txt AC 1471 ms 126840 KiB