No.2905 Nabeatsu Integration
タグ : / 解いたユーザー数 14
作問者 : 👑
amentorimaru
cleantted
👑
Nachia
Problem Statement
You are given a string $S$ consisting of digits.
In this problem, a real number $x\in [0,1)$ is regarded as an infinite decimal in base $10$. If the representation is not unique, take the one whose repeating part is $0$.
For example, $0.5$ has $2$ representations, $0.500000 \ldots$ and $0.499999 \ldots$, but in this problem it is regarded as $0.500000 \ldots$.
Define the function $f(x)\ (x\in [0,1))$ as follows: it is $0$ if $S$ does not appear in the digits after the decimal point of $x$, and it is $i$ if the first occurrence of $S$ in the digits after the decimal point of $x$ is from the $i$-th digit to the $(i+|S|-1)$-th digit after the decimal point.
Formally, the function $f(x)$ is defined on the interval $[0,1)$ as follows.
- Let $S_i$ be the $i$-th character $(1\leq i\leq |S|)$ of $S$, and let $N=\sum_{i=1}^{|S|} S_i 10^{|S|-i}$.
- Define the sequence of sets $I$ by $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)$. The elements of $I$ are pairwise disjoint.
- Let $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}$.
Find the value of the improper integral $\int_0^1 f(x)\mathrm{d}x$ modulo $\!\!\!\!\mod{998244353}$.
What "find the value modulo $\!\!\!\!\mod{998244353}$" means
It can be proved that the value to be found is always a rational number. Moreover, under the constraints of this problem, it can be proved that when the value is expressed as $P/Q$ using $2$ coprime integers $P,Q$, there exists exactly one integer $R$ such that $R\times Q\equiv P\ (\!\!\!\!\mod{998244353})$ and $0\leq R\lt 998244353$. Find this $R$.
Input
$S$
- $S$ is a string consisting of digits
- $1\leq |S|\leq 10^6$
Output
Output the value modulo $\!\!\!\!\mod{998244353}$, followed by a newline.
Sample
Sample 1
Input
3
Output
10
For $x$ that is at least $0.3$ and less than $0.4$, we have $f(x)=1$.
Also, for $x$ that is in any of the following ranges, we have $f(x)=2$: at least $0.03$ and less than $0.04$, at least $0.13$ and less than $0.14$, at least $0.23$ and less than $0.24$, at least $0.43$ and less than $0.44$, at least $0.53$ and less than $0.54$, at least $0.63$ and less than $0.64$, at least $0.73$ and less than $0.74$, at least $0.83$ and less than $0.84$, at least $0.93$ and less than $0.94$.
However, for $x$ that is at least $0.33$ and less than $0.34$, we have $f(x)=1$.
For $x$ such as $0.1,\ 0.4,\ 5/9=0.555555 \ldots$, the digit $3$ does not appear after the decimal point, so $f(x)=0$.
For this $f(x)$, we have $\int_0^1 f(x)\mathrm{d}x=10$.
Sample 2
Input
30
Output
99
$0.3$ is regarded as $0.300000 \ldots$. For $x$ that is at least $0.3$ and less than $0.31$, we have $f(x)=1$.
Also, for $x$ that is in any of the following ranges, we have $f(x)=2$: at least $0.03$ and less than $0.031$, at least $0.13$ and less than $0.131$, at least $0.23$ and less than $0.231$, at least $0.33$ and less than $0.331$, at least $0.43$ and less than $0.431$, at least $0.53$ and less than $0.531$, at least $0.63$ and less than $0.631$, at least $0.73$ and less than $0.731$, at least $0.83$ and less than $0.831$, at least $0.93$ and less than $0.931$.
For $x$ such as $0.1,\ 0.4,\ 5/9=0.555555 \ldots$, $30$ does not appear after the decimal point, so $f(x)=0$.
For this $f(x)$, we have $\int_0^1 f(x)\mathrm{d}x=99$.
Sample 3
Input
121212121212121212121212121212121212121
Output
43109500
Find the value of $\int_0^1 f(x)\mathrm{d}x$ modulo $\!\!\!\!\mod{998244353}$.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。