結果
問題 |
No.1646 Avoid Palindrome
|
ユーザー |
|
提出日時 | 2021-07-29 12:42:25 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 1,519 ms / 3,000 ms |
コード長 | 679 bytes |
コンパイル時間 | 452 ms |
コンパイル使用メモリ | 82,048 KB |
実行使用メモリ | 80,896 KB |
最終ジャッジ日時 | 2024-11-08 14:47:11 |
合計ジャッジ時間 | 41,447 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 40 |
ソースコード
n = int(input()) s = input() mod = 998244353 dp = [[0] * 27 for _ in range(27)] dp[-1][-1] = 1 for i in s: dp2 = [[0] * 27 for _ in range(27)] if i == "?": for i in range(27): i_sum = sum(dp[j][i] for j in range(27)) for j in range(26): if i == j: continue dp2[i][j] += i_sum - dp[j][i] else: char = ord(i) - ord("a") for i in range(27): for j in range(27): if i == char or j == char: continue dp2[j][char] += dp[i][j] dp = [[i % mod for i in j] for j in dp2] print(sum(map(sum, dp)) % mod)