結果
問題 |
No.2131 Concon Substrings (COuNt Version)
|
ユーザー |
![]() |
提出日時 | 2025-03-20 20:52:14 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 634 ms / 2,000 ms |
コード長 | 1,763 bytes |
コンパイル時間 | 177 ms |
コンパイル使用メモリ | 81,992 KB |
実行使用メモリ | 83,556 KB |
最終ジャッジ日時 | 2025-03-20 20:52:31 |
合計ジャッジ時間 | 5,163 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 16 |
ソースコード
import sys from collections import defaultdict MOD = 998244353 def main(): N = int(sys.stdin.readline()) prev_dp = [defaultdict(int) for _ in range(3)] prev_dp[0][0] = 1 # Initial state: 0 chars processed, state 0, k=0 for _ in range(N): next_dp = [defaultdict(int) for _ in range(3)] for s in range(3): for k in prev_dp[s]: count = prev_dp[s][k] if count == 0: continue if s == 0: # Transition for choosing 'c' next_s = 1 next_k = k next_dp[next_s][next_k] = (next_dp[next_s][next_k] + count) % MOD # Transition for others (25 possibilities) next_dp[0][k] = (next_dp[0][k] + count * 25) % MOD elif s == 1: # Transition for choosing 'o' next_s = 2 next_k = k next_dp[next_s][next_k] = (next_dp[next_s][next_k] + count) % MOD # Transition for others (25 possibilities) next_dp[1][k] = (next_dp[1][k] + count * 25) % MOD elif s == 2: # Transition for choosing 'n' next_s = 0 next_k = k + 1 next_dp[next_s][next_k] = (next_dp[next_s][next_k] + count) % MOD # Transition for others (25 possibilities) next_dp[2][k] = (next_dp[2][k] + count * 25) % MOD prev_dp = next_dp result = 0 for s in range(3): for k in prev_dp[s]: result = (result + k * prev_dp[s][k]) % MOD print(result) if __name__ == "__main__": main()