AT_abc338_g [ABC338G] evall

题目描述

给定一个字符串 $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$ 取模后输出。

输入格式

输入为一行，包含一个字符串 $S$。

输出格式

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

输入输出样例 #1

输入 #1

1+2*34

输出 #1

197

输入输出样例 #2

输入 #2

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

输出 #2

527930018

说明/提示

限制

• $1 \leq |S| \leq 10^6$
• $S$ 的每个字符都是 123456789+* 中的一个字符。
• $S$ 的首尾字符都是数字。
• $S$ 中不会有两个非数字字符相邻。

样例解释 1

$\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$。

由 ChatGPT 4.1 翻译