evall

题目描述

给你一个字符串 $S$。$S$ 的每个字符都是 1 到 9 或者 '+' 或 '*'，且 $S$ 的首尾字符是数字。$S$ 中不存在相邻的非数字字符。 对于一对整数 $i, j$（$1 \leq i \leq j \leq |S|$），我们定义 $\mathrm{eval}(S_{i..j})$ 如下：

如果 $S$ 的第 $i$ 个和第 $j$ 个字符都是数字，则 $\mathrm{eval}(S_{i..j})$ 是将第 $i$ 到第 $j$ 个字符（包括两端）作为通常的算术表达式（其中 $*$ 表示乘法）计算得到的结果。例如，如果 $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$ 取模。

输入格式

输入从标准输入给出，格式如下： $S$

输出格式

输出 ${\displaystyle \sum_{i=1}^{|S|} \sum_{j=i}^{|S|} \mathrm{eval}(S_{i..j})}$，对 $998244353$ 取模。

1+2*34

197

338*3338*33338*333338+3333338*33333338+333333338

527930018

提示

$1 \leq |S| \leq 10^6$ $S$ 的每个字符是 $123456789+*$ 之一。 $S$ 的首尾字符是数字。 $S$ 中不存在相邻的非数字字符。以下区间其 $\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$.

标签: AtCoder|abc338G

来源

AtCoder|abc338G