AT_abc224_f [ABC224F] Problem where +s Separate Digits

题目描述

给定一个只由 $1$ 到 $9$ 之间数字组成的字符串 $S$。
你可以通过以下操作从字符串 $S$ 构造一个表达式 $T$：

• 初始时，令 $T=S$。
• 选择一个集合 $A$，其中每个元素都是 $1$ 到 $|S|-1$ 之间的整数，且集合中的值互不相同。注意，$A$ 也可以是空集。
• 对于 $A$ 中的每个元素 $x$，按照 $x$ 从大到小的顺序，执行以下操作：
  • 在 $T$ 的第 $x$ 个字符和第 $x+1$ 个字符之间插入一个加号 +。

例如，当 $S=$ 1234，$A=\{2,3\}$ 时，$T=$ 12+3+4。

请你计算通过上述操作可以得到的所有可能的表达式 $T$ 的值之和，并输出该值对 $998244353$ 取模的结果。

输入格式

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

输出格式

请输出一个整数，表示答案。

输入输出样例 #1

输入 #1

1234

输出 #1

1736

输入输出样例 #2

输入 #2

1

输出 #2

1

输入输出样例 #3

输入 #3

31415926535897932384626433832795

输出 #3

85607943

说明/提示

限制条件

• $1 \leq |S| \leq 2 \times 10^5$
• $S$ 仅包含字符 1、2、3、4、5、6、7、8、9。

样例解释 1

所有可能的表达式 $T$ 为：1234、123+4、12+34、12+3+4、1+234、1+23+4、1+2+34、1+2+3+4，共 $8$ 个。它们的计算结果之和为 $1736$。

样例解释 2

$S$ 的长度也可能为 $1$。在这种情况下，$A$ 只能为一个空集。

样例解释 3

请输出答案对 $998244353$ 取模的结果。

由 ChatGPT 4.1 翻译