C - digitnum Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 300 点

問題文

整数 N が与えられるので、以下の問題を解いてください。

f(x)= ( x 以下の正整数で、 x と桁数が同じものの数) とします。
f(1)+f(2)+\dots+f(N) を 998244353 で割った余りを求めてください。

制約

  • N は整数
  • 1 \le N < 10^{18}

入力

入力は以下の形式で標準入力から与えられる。

N

出力

答えを整数として出力せよ。

入力例 1

16

出力例 1

73
  • 1 以上 9 以下の正整数 x について、 x 以下の整数で、 x と桁数が同じものは 1,2,\dots,x です。
    • これより、 f(1)=1,f(2)=2,...,f(9)=9 となります。
  • 10 以上 16 以下の正整数 x について、 x 以下の整数で、 x と桁数が同じものは 10,11,\dots,x です。
    • これより、 f(10)=1,f(11)=2,...,f(16)=7 となります。

結局、求める答えは 73 です。

入力例 2

238

出力例 2

13870

入力例 3

999999999999999999

出力例 3

762062362

998244353 で割った余りを求めることに注意してください。

Score : 300 points

Problem Statement

Given an integer N, solve the following problem.

Let f(x)= (The number of positive integers at most x with the same number of digits as x).
Find f(1)+f(2)+\dots+f(N) modulo 998244353.

Constraints

  • N is an integer.
  • 1 \le N < 10^{18}

Input

Input is given from Standard Input in the following format:

N

Output

Print the answer as an integer.

Sample Input 1

16

Sample Output 1

73
  • For a positive integer x between 1 and 9, the positive integers at most x with the same number of digits as x are 1,2,\dots,x.
    • Thus, we have f(1)=1,f(2)=2,...,f(9)=9.
  • For a positive integer x between 10 and 16, the positive integers at most x with the same number of digits as x are 10,11,\dots,x.
    • Thus, we have f(10)=1,f(11)=2,...,f(16)=7.

The final answer is 73.

Sample Input 2

238

Sample Output 2

13870

Sample Input 3

999999999999999999

Sample Output 3

762062362

Be sure to find the sum modulo 998244353.