結果
問題 | No.2019 Digits Filling for All Substrings |
ユーザー |
![]() |
提出日時 | 2022-07-22 22:57:28 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 211 ms / 2,000 ms |
コード長 | 968 bytes |
コンパイル時間 | 290 ms |
コンパイル使用メモリ | 82,312 KB |
実行使用メモリ | 96,768 KB |
最終ジャッジ日時 | 2024-07-04 07:31:37 |
合計ジャッジ時間 | 4,758 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 30 |
ソースコード
from itertools import product n = int(input()) S = input() mod = 998244353 def count(s): a = s n = len(a) ret = 0 #配列は末から dp=[[0] * 3 for _ in range(n+1) ] for i in range(n) : if a[i]=='?': max_d = 9 for d in range(max_d+1): mod3_ = d % 3 dp[i + 1][mod3_] += 1 else: d = int(a[i]) mod3_ = d % 3 dp[i + 1][mod3_] += 1 #条件に合わせてDP for mod3 in range(3): if a[i]=='?': max_d = 9 for d in range(max_d+1): mod3_ = (mod3*10 + d) % 3 dp[i + 1][mod3_] = (dp[i + 1][mod3_]+dp[i][mod3])%mod else: d = int(a[i]) mod3_ = (mod3*10 + d) % 3 dp[i + 1][mod3_] = (dp[i + 1][mod3_]+dp[i][mod3])%mod ret = (ret+dp[i+1][0])%mod return ret%mod print(count(S))