No.2019 Digits Filling for All Substrings
タグ : / 解いたユーザー数 69
作問者 :
Shirotsume
/ テスター :
37zigen
問題文
数字 0-9 および ? からなる文字列 $X$ に対し、以下の問題の答えを $f(X)$ とします。
問題: $X$ に含まれる ? をそれぞれ 数字 0-9 のうち $1$ 文字に置き替えてできる文字列 $X'$ を考えます。$X'$ としてありうる文字列は $X$ に含まれる ? の数を $k$ 個とすると $10^k$ 通りありますが、そのうち先頭の不要な $0$ を取り除いて整数とみなしたとき $3$ の倍数となるものはいくつありますか？
また、文字列 $S$ について $S$ の $L$ 文字目から $R$ 文字目までで構成される連続部分文字列を $S[L:R]$ として表します。
数字 0-9 および ? からなる長さ $N$ の文字列 $S$ が与えられるので、 $\displaystyle \sum_{L = 1}^{N} \sum_{R = L}^{N} f(S[L:R])$ を $998244353$ で割ったあまりを求めてください。
制約
- 入力は全て整数
- $1 \leq N \leq 2 \times 10^5$
- $S$ は数字
0-9および?からなる長さ $N$ の文字列
入力
入力は以下の形式で標準入力から与えられる。$N$ $S$
出力
答えを出力せよ。最後に改行すること。
サンプル
サンプル1
入力
3 1?3
出力
15
$S$ の空でない部分文字列それぞれについて $f$ の値を示します。
- $S[1:1] =$
1について、 $f(S[1:1]) = 0$ です。 - $S[2:2] =$
?について、?を0-9に置き替えて作れる $3$ の倍数は $0, 3, 6, 9$ の $4$ つであることから、 $f(S[2:2]) = 4$ です。 - $S[3:3] =$
3について、 $f(S[3:3]) = 1$ です。 - $S[1:2] =$
1?について、 作れる $3$ の倍数は $12, 15, 18$ の $3$ つなので $f(S[1:2]) = 3$ です。 - $S[2:3] =$
?3について、 作れる $3$ の倍数は $3, 33, 63, 93$ の $4$ つなので $f(S[2:3]) = 4$ です。先頭が $0$ となっても構いません。 - $S[1:3] =$
1?3について、 作れる $3$ の倍数は $123, 153, 183$ の $3$ つなので $f(S[1:3]) = 3$ です。
よって、求める答えは $0 + 4 + 1 + 3 + 4 + 3 = 15$ となります。
サンプル2
入力
5 12345
出力
7
$S$ に ? が含まれていない場合があります。
サンプル3
入力
3 ???
出力
414
$S$ が ? のみからなる場合もあります。
サンプル4
入力
32 31415926????????23846264????????
出力
945855420
$998244353$ で割ったあまりを求めてください。
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。