← 返回题目列表

AtCoder · abc338_g

G. 评估

中文机器翻译题面 查看原题

分数: 600 点

问题陈述

给你一个字符串 S。的每个字符 S 是其中之一 123456789+*,以及第一个和最后一个字符 S 是数字。中没有相邻的非数字字符 S.

对于一对整数 i, j (1 \leq i \leq j \leq |S|),我们定义 \mathrm{eval}(S_{i..j}) 如下:

  • 如果两者 i-th 和 j第一个字符 S 是数字,那么 \mathrm{eval}(S_{i..j}) 是评估的结果 i-第 j第一个字符(含) S 作为通常的算术表达式(其中 * 代表乘法)。例如,如果 S = 1+2*151,那么 \mathrm{eval}(S_{1..6}) = 1 + 2 \times 15 = 31.
  • 否则, \mathrm{eval}(S_{i..j}) 为零。

查找 {\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}) 不为零的情况如下:

  • \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