結果
問題 |
No.1646 Avoid Palindrome
|
ユーザー |
![]() |
提出日時 | 2022-12-10 15:23:09 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 996 ms / 3,000 ms |
コード長 | 1,260 bytes |
コンパイル時間 | 248 ms |
コンパイル使用メモリ | 82,412 KB |
実行使用メモリ | 77,136 KB |
最終ジャッジ日時 | 2024-10-14 23:41:33 |
合計ジャッジ時間 | 21,381 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 40 |
ソースコード
N = int(input()) S = input() if N==1: print(26 if S[0]=='?' else 1) exit() def f(s): return ord(s)-97 mod = 998244353 dp = [[0]*26 for _ in range(26)] if S[0]=='?' and S[1]=='?': for i in range(26): for j in range(26): if i==j:continue dp[i][j] = 1 elif S[0]=='?': s = f(S[1]) for i in range(26): if i==s:continue dp[i][s] = 1 elif S[1]=='?': s = f(S[0]) for i in range(26): if i==s:continue dp[s][i] = 1 else: s1, s2 = f(S[0]), f(S[1]) dp[s1][s2] = 1 for i in range(2,N): ndp = [[0]*26 for _ in range(26)] sm = [0]*26 for j in range(26): for k in range(26): if j==k:continue sm[k] += dp[j][k] sm[k] %= mod if S[i]=='?': for j in range(26): for k in range(26): if j==k:continue ndp[j][k] += sm[j]-dp[k][j] ndp[j][k] %= mod else: s = f(S[i]) for j in range(26): ndp[j][s] += sm[j]-dp[s][j] ndp[j][s] %= mod dp = ndp res = 0 for i in range(26): for j in range(26): if i==j:continue res += dp[i][j] res %= mod print(res)