結果
問題 |
No.1646 Avoid Palindrome
|
ユーザー |
![]() |
提出日時 | 2023-03-27 08:59:38 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 508 ms / 3,000 ms |
コード長 | 1,628 bytes |
コンパイル時間 | 432 ms |
コンパイル使用メモリ | 82,144 KB |
実行使用メモリ | 78,720 KB |
最終ジャッジ日時 | 2024-09-19 10:07:22 |
合計ジャッジ時間 | 14,389 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 40 |
ソースコード
N = int(input()) S = list(input()) mod = 998244353 def f(a, b): return a * 26 + b if N == 1: if S[0] == "?": print(26) else: print(1) exit() pre = [0] * (26 * 26) Spre = [0] * 26 if S[0] == S[1] == "?": for a in range(26): for b in range(26): if a == b: continue pre[f(a,b)] = 1 Spre[b] += 1 elif S[0] == "?": b = ord(S[1]) - ord("a") for a in range(26): if a == b: continue pre[f(a,b)] = 1 Spre[b] += 1 elif S[1] == "?": a = ord(S[0]) - ord("a") for b in range(26): if a == b: continue pre[f(a,b)] = 1 Spre[b] += 1 else: if S[0] == S[1]: print(0) exit() a = ord(S[0]) - ord("a") b = ord(S[1]) - ord("a") pre[f(a,b)] = 1 Spre[b] += 1 for i in range(2, N): dp = [0] * (26 * 26) Sdp = [0] * 26 if S[i] == "?": for a in range(26): for b in range(26): if a == b: continue dp[f(a,b)] += Spre[a] - pre[f(b,a)] dp[f(a,b)] %= mod Sdp[b] += dp[f(a,b)] Sdp[b] %= mod else: b = ord(S[i]) - ord("a") for a in range(26): if a == b: continue dp[f(a,b)] += Spre[a] - pre[f(b,a)] dp[f(a,b)] %= mod Sdp[b] += dp[f(a,b)] Sdp[b] %= mod pre, dp = dp, pre Spre, Sdp = Sdp, Spre ans = 0 for a in range(26): for b in range(26): ans += pre[f(a,b)] ans %= mod print(ans)