No.2905 Nabeatsu Integration
タグ : / 解いたユーザー数 8
作問者 : 👑
amentorimaru
cleantted
👑 
Nachia
問題文
数字からなる文字列 $S$ が与えられます。
この問題では、実数 $x\in [0,1)$ を $10$ 進の無限小数として考えます。一意に表せない場合は、循環節が $0$ となるものをとります。
たとえば、 $0.5$ は $0.500000 \ldots$ と $0.499999 \ldots$ の $2$ 通りの表し方がありますが、この問題では $0.500000 \ldots$ として考えます。
関数 $f(x)\ (x\in [0,1))$ を「 $x$ の小数点以下に $S$ が現れないならば $0$ 、 $x$ の小数点以下に $S$ が初めて現れるのが小数点以下 $i$ 桁目から $(i+|S|-1)$ 桁目である場合は $i$ 」と定義します。
厳密には、関数 $f(x)$ は区間 $[0,1)$ で以下のように定義されます。
- $S$ の $i$ 文字目 $(1\leq i\leq |S|)$ を $S_i$ とし、 $N=\sum_{i=1}^{|S|} S_i 10^{|S|-i}$ とおく。
- 集合の列 $I$ を、 $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)$ として定義する。 $I$ の要素は互いに交わらない。
- $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}$ とする。
広義積分 $\int_0^1 f(x)\mathrm{d}x$ の値を $\!\!\!\!\mod{998244353}$ で求めてください。
「値を $\!\!\!\!\mod{998244353}$ で求める」とは
求める値は必ず有理数となることが証明できます。またこの問題の制約下では、その値を互いに素な $2$ つの整数 $P,Q$ を用いて $P/Q$ と表したとき、 $R\times Q\equiv P\ (\!\!\!\!\mod{998244353})$ かつ $0\leq R\lt 998244353$ を満たす整数 $R$ がただ一つ存在することが証明できます。この $R$ を求めてください。
入力
$S$
- $S$ は数字ならなる文字列
- $1\leq |S|\leq 10^6$
出力
値を $\!\!\!\!\mod{998244353}$ で出力し、最後に改行してください。
サンプル
サンプル1
入力
3
出力
10
$0.3$ 以上 $0.4$ 未満の $x$ について、 $f(x)=1$ となります。
また、 $0.03$ 以上 $0.04$ 未満、 $0.13$ 以上 $0.14$ 未満、 $0.23$ 以上 $0.24$ 未満、 $0.43$ 以上 $0.44$ 未満、 $0.53$ 以上 $0.54$ 未満、 $0.63$ 以上 $0.64$ 未満、 $0.73$ 以上 $0.74$ 未満、 $0.83$ 以上 $0.84$ 未満、 $0.93$ 以上 $0.94$ 未満のいずれかである $x$ について、 $f(x)=2$ となります。
ただし、 $0.33$ 以上 $0.34$ 未満の $x$ については $f(x)=1$ となります。
$0.1,\ 0.4,\ 5/9=0.555555 \ldots$ などの $x$ については、小数点以下に $3$ が現れないため $f(x)=0$ となります。
このような $f(x)$ について、 $\int_0^1 f(x)\mathrm{d}x=10$ となります。
サンプル2
入力
30
出力
99
$0.3$ は $0.300000 \ldots$ として考えます。 $0.3$ 以上 $0.31$ 未満の $x$ について、 $f(x)=1$ となります。
また、 $0.03$ 以上 $0.031$ 未満、 $0.13$ 以上 $0.131$ 未満、 $0.23$ 以上 $0.231$ 未満、 $0.33$ 以上 $0.331$ 未満、 $0.43$ 以上 $0.431$ 未満、 $0.53$ 以上 $0.531$ 未満、 $0.63$ 以上 $0.631$ 未満、 $0.73$ 以上 $0.731$ 未満、 $0.83$ 以上 $0.831$ 未満、 $0.93$ 以上 $0.931$ 未満のいずれかである $x$ について、 $f(x)=2$ となります。
$0.1,\ 0.4,\ 5/9=0.555555 \ldots$ などの $x$ については、小数点以下に $30$ が現れないため $f(x)=0$ となります。
このような $f(x)$ について、 $\int_0^1 f(x)\mathrm{d}x=99$ となります。
サンプル3
入力
121212121212121212121212121212121212121
出力
43109500
$\int_0^1 f(x)\mathrm{d}x$ の値を $\!\!\!\!\mod{998244353}$ で求めてください。
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。