分数: 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