F - Problem where +s Separate Digits Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 500 点

問題文

1 から 9 までの数字のみで構成された文字列 S が与えられます。
この文字列 S から、以下の操作によって式 T を作ります。

  • はじめ、 T=S であるとする。
  • 各要素が 1 以上 |S|-1 以下の整数である、値に重複のない集合 A を選ぶ。なお、 A が空集合であってもよい。
  • A の全ての要素 x について、 x の降順に以下の操作を行う。
    • T の x 文字目と x+1 文字目の間に、 + を挿入する。

例えば、 S= 1234、 A= \lbrace 2,3 \rbrace であるとき、 T= 12+3+4 となります。

この操作によって得られる T としてあり得る全ての式に対して、式を計算したときの値の総和を 998244353 で割った余りを求めてください。

制約

  • 1 \le |S| \le 2 \times 10^5
  • S は 1, 2, 3, 4, 5, 6, 7, 8, 9 のみからなる。

入力

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

S

出力

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

入力例 1

1234

出力例 1

1736

式 T としてあり得るものは 1234, 123+4, 12+34, 12+3+4, 1+234, 1+23+4, 1+2+34, 1+2+3+4 の 8 つです。
これらを計算した値の総和は 1736 です。

入力例 2

1

出力例 2

1

S の長さが 1 であることもあります。この場合、 A として指定可能なのは空集合のみです。

入力例 3

31415926535897932384626433832795

出力例 3

85607943

答えを 998244353 で割った余りを求めてください。

Score : 500 points

Problem Statement

Given is a string S consisting of digits from 1 through 9.
From this string S, let us make a formula T by the following operations.

  • Initially, let T=S.
  • Choose a (possibly empty) set A of different integers where each element is between 1 and |S|-1 (inclusive).
  • For each element x in descending order, do the following.
    • Insert a + between the x-th and (x+1)-th characters of T.

For example, when S= 1234 and A= \lbrace 2,3 \rbrace, we will have T= 12+3+4.

Consider evaluating all possible formulae T obtained by these operations. Find the sum, modulo 998244353, of the evaluations.

Constraints

  • 1 \le |S| \le 2 \times 10^5
  • S consists of 1, 2, 3, 4, 5, 6, 7, 8, and 9.

Input

Input is given from Standard Input in the following format:

S

Output

Print the answer.

Sample Input 1

1234

Sample Output 1

1736

There are eight formulae that can be obtained as T: 1234, 123+4, 12+34, 12+3+4, 1+234, 1+23+4, 1+2+34, and 1+2+3+4.
The sum of the evaluations of these formulae is 1736.

Sample Input 2

1

Sample Output 2

1

S may have a length of 1, in which case the only possible choice for A is the empty set.

Sample Input 3

31415926535897932384626433832795

Sample Output 3

85607943

Be sure to find the sum modulo 998244353.