提出 #53276051

ソースコード 拡げる

N = int(input())
S = input()
mod = 998244353
# dp[i][S][j] := i 番目までのコンテストで、集合が S で最後のコンテストが j の時の組み合わせ
dp = [[[0]*10 for _ in range(1 << 10)] for _ in range(N + 1)]
for i in range(N):
    dp[i + 1][1 << (ord(S[i]) - ord("A"))][ord(S[i]) - ord("A")] = 1

for i in range(N):
    for s in range(1 << 10):
        for j in range(10):
            # その文字を選ばない場合
            dp[i + 1][s][j] += dp[i][s][j]
            dp[i + 1][s][j] %= mod
            nxt = ord(S[i]) - ord("A")
            # 同じ文字 or 集合に nxt が含まれてない場合に遷移する
            if nxt == j or not (s >> nxt) & 1:
                dp[i + 1][s | (1 << nxt)][nxt] += dp[i][s][j]
                dp[i + 1][s | (1 << nxt)][nxt] %= mod

ans = 0
for s in range(1 << 10):
    for j in range(10):
        ans += dp[N][s][j]
        ans %= mod

print(ans)

提出情報

提出日時
問題 E - Chain Contestant
ユーザ ryusuke_h
言語 Python (PyPy 3.10-v7.3.12)
得点 500
コード長 953 Byte
結果 AC
実行時間 446 ms
メモリ 237344 KiB

ジャッジ結果

セット名 Sample All
得点 / 配点 0 / 0 500 / 500
結果
AC × 2
AC × 22
セット名 テストケース
Sample sample_01.txt, sample_02.txt
All sample_01.txt, sample_02.txt, test_01.txt, test_02.txt, test_03.txt, test_04.txt, test_05.txt, test_06.txt, test_07.txt, test_08.txt, test_09.txt, test_10.txt, test_11.txt, test_12.txt, test_13.txt, test_14.txt, test_15.txt, test_16.txt, test_17.txt, test_18.txt, test_19.txt, test_20.txt
ケース名 結果 実行時間 メモリ
sample_01.txt AC 77 ms 82808 KiB
sample_02.txt AC 113 ms 99292 KiB
test_01.txt AC 69 ms 82152 KiB
test_02.txt AC 348 ms 204032 KiB
test_03.txt AC 91 ms 88792 KiB
test_04.txt AC 254 ms 162348 KiB
test_05.txt AC 133 ms 107832 KiB
test_06.txt AC 144 ms 111448 KiB
test_07.txt AC 291 ms 176928 KiB
test_08.txt AC 268 ms 167208 KiB
test_09.txt AC 384 ms 219364 KiB
test_10.txt AC 386 ms 221828 KiB
test_11.txt AC 422 ms 237132 KiB
test_12.txt AC 417 ms 237112 KiB
test_13.txt AC 418 ms 237300 KiB
test_14.txt AC 419 ms 236920 KiB
test_15.txt AC 436 ms 236896 KiB
test_16.txt AC 417 ms 236900 KiB
test_17.txt AC 419 ms 236712 KiB
test_18.txt AC 414 ms 237344 KiB
test_19.txt AC 413 ms 236992 KiB
test_20.txt AC 446 ms 236984 KiB