問題一覧 > 通常問題

No.2019 Digits Filling for All Substrings

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

問題文

数字 0-9 および ? からなる文字列 XX に対し、以下の問題の答えを f(X)f(X) とします。

    問題: XX に含まれる ? をそれぞれ 数字 0-9 のうち 11 文字に置き替えてできる文字列 X′X' を考えます。X′X' としてありうる文字列は XX に含まれる ? の数を kk 個とすると 10k10^k 通りありますが、そのうち先頭の不要な 00 を取り除いて整数とみなしたとき 33 の倍数となるものはいくつありますか？

また、文字列 SS について SS の LL 文字目から RR 文字目までで構成される連続部分文字列を S[L:R]S[L:R] として表します。

数字 0-9 および ? からなる長さ NN の文字列 SS が与えられるので、 ∑L=1N∑R=LNf(S[L:R])\displaystyle \sum_{L = 1}^{N} \sum_{R = L}^{N} f(S[L:R]) を 998244353998244353 で割ったあまりを求めてください。

制約

  • 入力は全て整数
  • 1≤N≤2×1051 \leq N \leq 2 \times 10^5
  • SS は数字 0-9 および ? からなる長さ NN の文字列

入力

入力は以下の形式で標準入力から与えられる。 
NN
SS

出力

答えを出力せよ。最後に改行すること。

サンプル

サンプル1
入力
3
1?3
出力
15

SS の空でない部分文字列それぞれについて ff の値を示します。

  • S[1:1]=S[1:1] = 1 について、 f(S[1:1])=0f(S[1:1]) = 0 です。
  • S[2:2]=S[2:2] = ? について、? を 0-9 に置き替えて作れる 33 の倍数は 0,3,6,90, 3, 6, 9 の 44 つであることから、 f(S[2:2])=4f(S[2:2]) = 4 です。
  • S[3:3]=S[3:3] = 3 について、 f(S[3:3])=1f(S[3:3]) = 1 です。
  • S[1:2]=S[1:2] = 1? について、 作れる 33 の倍数は 12,15,1812, 15, 18 の 33 つなので f(S[1:2])=3f(S[1:2]) = 3 です。
  • S[2:3]=S[2:3] = ?3 について、 作れる 33 の倍数は 3,33,63,933, 33, 63, 93 の 44 つなので f(S[2:3])=4f(S[2:3]) = 4 です。先頭が 00 となっても構いません。
  • S[1:3]=S[1:3] = 1?3 について、 作れる 33 の倍数は 123,153,183123, 153, 183 の 33 つなので f(S[1:3])=3f(S[1:3]) = 3 です。

よって、求める答えは 0+4+1+3+4+3=150 + 4 + 1 + 3 + 4 + 3 = 15 となります。

サンプル2
入力
5
12345
出力
7

SS に ? が含まれていない場合があります。

サンプル3
入力
3
???
出力
414

SS が ? のみからなる場合もあります。

サンプル4
入力
32
31415926????????23846264????????
出力
945855420

998244353998244353 で割ったあまりを求めてください。

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。