問題一覧 > 通常問題

No.2905 Nabeatsu Integration

レベル : / AI推定難易度 : 1875 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 128 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 14
作問者 : 👑 獅子座じゃない人 / テスター : 👑 amentorimaru cleantted 👑 Nachia
お気に入りにしたユーザー ProblemId : 10896 / 自分の提出
問題文最終更新日: 2024-09-26 23:01:32
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 448 (順位表) の他の問題:

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