問題一覧 > 通常問題

No.2019 Digits Filling for All Substrings

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 61
作問者 : ShirotsumeShirotsume / テスター : 37zigen37zigen
1 ProblemId : 7678 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2022-04-25 13:20:00

問題文

数字 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もしくは右上の雲マークをクリックしてアカウントを作成してください。