No.3242 Count 8 Included Numbers (Hard)
タグ : / 解いたユーザー数 103
作問者 : 👑
p-adic
ygussany
Problem Statement
This problem has the same setting as Count 8 Included Numbers (Easy) (Problem A of the contest), and differs only in the constraints and some other details.
By submitting code that is correct for this problem, you can also get Accepted on Count 8 Included Numbers (Easy).
AngrySadEight loves the digit $8$. So, they decided to count how many numbers contain $8$.
Find how many positive integers less than or equal to $N$ contain the digit $8$ in their decimal representation.
However, since the answer can be very large, output the answer modulo $998244353$.
Constraints
- $N$ is an integer
- $1 \leq N < 10^{888888}$
Input
The input is given from standard input in the following format.
$N$
Output
Output the answer modulo $998244353$.
Sample
Sample 1
Input
8
Output
1
The positive integers less than or equal to $8$ that contain $8$ are just $8$, which is $1$ number. Therefore, output $1$.
Sample 2
Input
88
Output
17
The positive integers less than or equal to $88$ that contain $8$ are $8, 18, 28, 38, 48, 58, 68, 78, 80, 81, 82, 83, 84, 85, 86, 87, 88$, which is $17$ numbers. Therefore, output $17$.
Sample 3
Input
1
Output
0
There are no positive integers less than or equal to $1$ that contain $8$. Therefore, output $0$.
Sample 4
Input
888
Output
241
Sample 5
Input
888888888888888888888888
Output
241265183
Note that the input may not fit in a $64$-bit integer. Also, output the answer modulo $998244353$.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。