問題一覧 > 通常問題

No.2905 Nabeatsu Integration

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 128 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 13
作問者 : 👑 獅子座じゃない人 / テスター : 👑 amentorimaru cleantted 👑 Nachia
2 ProblemId : 10896 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2024-09-26 23:01:32

問題文

数字からなる文字列 SS が与えられます。

この問題では、実数 x∈[0,1)x\in [0,1) を 1010 進の無限小数として考えます。一意に表せない場合は、循環節が 00 となるものをとります。

たとえば、 0.50.5 は 0.500000…0.500000 \ldots と 0.499999…0.499999 \ldots の 22 通りの表し方がありますが、この問題では 0.500000…0.500000 \ldots として考えます。

関数 f(x) (x∈[0,1))f(x)\ (x\in [0,1)) を「 xx の小数点以下に SS が現れないならば 00 、 xx の小数点以下に SS が初めて現れるのが小数点以下 ii 桁目から (i+∣S∣−1)(i+|S|-1) 桁目である場合は ii 」と定義します。

厳密には、関数 f(x)f(x) は区間 [0,1)[0,1) で以下のように定義されます。

  • SS の ii 文字目 (1≤i≤∣S∣)(1\leq i\leq |S|) を SiS_i とし、 N=∑i=1∣S∣Si10∣S∣−iN=\sum_{i=1}^{|S|} S_i 10^{|S|-i} とおく。
  • 集合の列 II を、 I1=[N/10∣S∣,(N+1)/10∣S∣), Ii+1=⋃k=010i−1[k/10i+N/10∣S∣+i,k/10i+(N+1)/10∣S∣+i)∖⋃k=1iIk (i≥1)I_1=[N/10^{|S|},(N+1)/10^{|S|}),\ I_{i+1}=\bigcup_{k=0}^{10^i-1} [k/10^i+N/10^{|S|+i},k/10^i+(N+1)/10^{|S|+i})\setminus \bigcup_{k=1}^{i} I_k\ (i\geq 1) として定義する。 II の要素は互いに交わらない。
  • f(x)={i (x∈Ii, i≥1)0 (x∈[0,1)∖⋃k=1∞Ik)f(x)=\begin{cases}i\ (x\in I_i,\ i\geq 1)\\0\ \left(x\in [0,1)\setminus\bigcup_{k=1}^{\infty} I_k\right)\end{cases} とする。

広義積分 ∫01f(x)dx\int_0^1 f(x)\mathrm{d}x の値を  ⁣ ⁣ ⁣ ⁣mod  998244353\!\!\!\!\mod{998244353} で求めてください。

「値を  ⁣ ⁣ ⁣ ⁣mod  998244353\!\!\!\!\mod{998244353} で求める」とは

求める値は必ず有理数となることが証明できます。またこの問題の制約下では、その値を互いに素な 22 つの整数 P,QP,Q を用いて P/QP/Q と表したとき、 R×Q≡P ( ⁣ ⁣ ⁣ ⁣mod  998244353)R\times Q\equiv P\ (\!\!\!\!\mod{998244353}) かつ 0≤R<9982443530\leq R\lt 998244353 を満たす整数 RR がただ一つ存在することが証明できます。この RR を求めてください。

入力

SS

  • SS は数字ならなる文字列
  • 1≤∣S∣≤1061\leq |S|\leq 10^6

出力

値を  ⁣ ⁣ ⁣ ⁣mod  998244353\!\!\!\!\mod{998244353} で出力し、最後に改行してください。

サンプル

サンプル1
入力
3
出力
10

0.30.3 以上 0.40.4 未満の xx について、 f(x)=1f(x)=1 となります。

また、 0.030.03 以上 0.040.04 未満、 0.130.13 以上 0.140.14 未満、 0.230.23 以上 0.240.24 未満、 0.430.43 以上 0.440.44 未満、 0.530.53 以上 0.540.54 未満、 0.630.63 以上 0.640.64 未満、 0.730.73 以上 0.740.74 未満、 0.830.83 以上 0.840.84 未満、 0.930.93 以上 0.940.94 未満のいずれかである xx について、 f(x)=2f(x)=2 となります。

ただし、 0.330.33 以上 0.340.34 未満の xx については f(x)=1f(x)=1 となります。

0.1, 0.4, 5/9=0.555555…0.1,\ 0.4,\ 5/9=0.555555 \ldots などの xx については、小数点以下に 33 が現れないため f(x)=0f(x)=0 となります。

このような f(x)f(x) について、 ∫01f(x)dx=10\int_0^1 f(x)\mathrm{d}x=10 となります。

サンプル2
入力
30
出力
99

0.30.3 は 0.300000…0.300000 \ldots として考えます。 0.30.3 以上 0.310.31 未満の xx について、 f(x)=1f(x)=1 となります。

また、 0.030.03 以上 0.0310.031 未満、 0.130.13 以上 0.1310.131 未満、 0.230.23 以上 0.2310.231 未満、 0.330.33 以上 0.3310.331 未満、 0.430.43 以上 0.4310.431 未満、 0.530.53 以上 0.5310.531 未満、 0.630.63 以上 0.6310.631 未満、 0.730.73 以上 0.7310.731 未満、 0.830.83 以上 0.8310.831 未満、 0.930.93 以上 0.9310.931 未満のいずれかである xx について、 f(x)=2f(x)=2 となります。

0.1, 0.4, 5/9=0.555555…0.1,\ 0.4,\ 5/9=0.555555 \ldots などの xx については、小数点以下に 3030 が現れないため f(x)=0f(x)=0 となります。

このような f(x)f(x) について、 ∫01f(x)dx=99\int_0^1 f(x)\mathrm{d}x=99 となります。

サンプル3
入力
121212121212121212121212121212121212121
出力
43109500

∫01f(x)dx\int_0^1 f(x)\mathrm{d}x の値を  ⁣ ⁣ ⁣ ⁣mod  998244353\!\!\!\!\mod{998244353} で求めてください。

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