Problem where +s Separate Digits

题目描述

给定一个由数字 $1$ 到 $9$ 组成的字符串 $S$。
从该字符串 $S$，通过以下操作构造一个表达式 $T$。

最初，令 $T=S$。 选择一个（可能为空的）不同整数集合 $A$，其中每个元素在 $1$ 到 $|S|-1$（含）之间。 对于集合中按降序排列的每个元素 $x$，执行以下操作。 在 $T$ 的第 $x$ 个和第 $x+1$ 个字符之间插入一个 $+$。

例如，当 $S=$ $1234$ 且 $A= \lbrace 2,3 \rbrace$ 时，我们将得到 $T$= $12+3+4$。 考虑对通过这些操作得到的所有可能的表达式 $T$ 进行求值。求这些求值结果的和，对 $998244353$ 取模。

输入格式

从标准输入给出如下格式的数据： $S$

输出格式

输出答案。

1234

1736

1

1

31415926535897932384626433832795

85607943

提示

$1 \le |S| \le 2 \times 10^5$ $S$ 由 $1,2,3,4,5,6,7,8,9$ 组成。可以得到的 $T$ 有八种：$1234$, $123+4$, $12+34$, $12+3+4$, $1+234$, $1+23+4$, $1+2+34$, 和 $1+2+3+4$.
这些表达式的求和值为 $1736$.
$S$ 的长度可能为 $1$，此时 $A$ 唯一可能的选择是空集。
请注意对 $998244353$ 取模。

标签: AtCoder|abc224F

来源

AtCoder|abc224F