/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 600 点
問題文
文字列 S が与えられます。S の各文字は 123456789+* のいずれかで、S の先頭と末尾の文字は数字であり、S の中で数字でない文字どうしが隣接することはありません。
整数の組 i, j（1 \leq i \leq j \leq |S|）に対して、\mathrm{eval}(S_{i..j}) を以下のように定義します。
- S の i 文字目と j 文字目がともに数字であれば、\mathrm{eval}(S_{i..j}) は S の i 文字目から j 文字目まで（両端含む）を通常の数式として評価した結果とする（
*は乗算とする）。例えば、S =1+2*151のとき、\mathrm{eval}(S_{1..6}) = 1 + 2 \times 15 = 31 である。 - そうでなければ、\mathrm{eval}(S_{i..j}) は 0 とする。
{\displaystyle \sum_{i=1}^{|S|} \sum_{j=i}^{|S|} \mathrm{eval}(S_{i..j})} を 998244353 で割ったあまりを求めてください。
制約
- 1 \leq |S| \leq 10^6
- S の各文字は
123456789+*のいずれかである。 - S の先頭と末尾の文字は数字である。
- S の中で数字でない文字どうしが隣接することはない。
入力
入力は以下の形式で標準入力から与えられる。
S
出力
{\displaystyle \sum_{i=1}^{|S|} \sum_{j=i}^{|S|} \mathrm{eval}(S_{i..j})} を 998244353 で割ったあまりを出力せよ。
入力例 1
1+2*34
出力例 1
197
\mathrm{eval}(S_{i..j}) が 0 でない場合は以下の通りです。
- \mathrm{eval}(S_{1..1}) = 1
- \mathrm{eval}(S_{1..3}) = 1 + 2 = 3
- \mathrm{eval}(S_{1..5}) = 1 + 2 \times 3 = 7
- \mathrm{eval}(S_{1..6}) = 1 + 2 \times 34 = 69
- \mathrm{eval}(S_{3..3}) = 2
- \mathrm{eval}(S_{3..5}) = 2 \times 3 = 6
- \mathrm{eval}(S_{3..6}) = 2 \times 34 = 68
- \mathrm{eval}(S_{5..5}) = 3
- \mathrm{eval}(S_{5..6}) = 34
- \mathrm{eval}(S_{6..6}) = 4
以上の合計は 1+3+7+69+2+6+68+3+34+4 = 197 です。
入力例 2
338*3338*33338*333338+3333338*33333338+333333338
出力例 2
527930018
Score: 600 points
Problem Statement
You are given a string S. Each character of S is one of 123456789+*, and the first and last characters of S are digits. There are no adjacent non-digit characters in S.
For a pair of integers i, j (1 \leq i \leq j \leq |S|), we define \mathrm{eval}(S_{i..j}) as follows:
- If both the i-th and j-th characters of S are digits, then \mathrm{eval}(S_{i..j}) is the result of evaluating the i-th to the j-th characters (inclusive) of S as a usual arithmetic expression (where
*represents multiplication). For example, if S =1+2*151, then \mathrm{eval}(S_{1..6}) = 1 + 2 \times 15 = 31. - Otherwise, \mathrm{eval}(S_{i..j}) is zero.
Find {\displaystyle \sum_{i=1}^{|S|} \sum_{j=i}^{|S|} \mathrm{eval}(S_{i..j})}, modulo 998244353.
Constraints
- 1 \leq |S| \leq 10^6
- Each character of S is one of
123456789+*. - The first and last characters of S are digits.
- There are no adjacent non-digit characters in S.
Input
The input is given from Standard Input in the following format:
S
Output
Print {\displaystyle \sum_{i=1}^{|S|} \sum_{j=i}^{|S|} \mathrm{eval}(S_{i..j})}, modulo 998244353.
Sample Input 1
1+2*34
Sample Output 1
197
The cases where \mathrm{eval}(S_{i..j}) is not zero are as follows:
- \mathrm{eval}(S_{1..1}) = 1
- \mathrm{eval}(S_{1..3}) = 1 + 2 = 3
- \mathrm{eval}(S_{1..5}) = 1 + 2 \times 3 = 7
- \mathrm{eval}(S_{1..6}) = 1 + 2 \times 34 = 69
- \mathrm{eval}(S_{3..3}) = 2
- \mathrm{eval}(S_{3..5}) = 2 \times 3 = 6
- \mathrm{eval}(S_{3..6}) = 2 \times 34 = 68
- \mathrm{eval}(S_{5..5}) = 3
- \mathrm{eval}(S_{5..6}) = 34
- \mathrm{eval}(S_{6..6}) = 4
The sum of these is 1+3+7+69+2+6+68+3+34+4 = 197.
Sample Input 2
338*3338*33338*333338+3333338*33333338+333333338
Sample Output 2
527930018