题解

思路

连续数字必然整体构成一个整数，可先压缩为一个记号。+、- 在计数意义下相同，*、/ 也相同。若 * 或 / 出现在开头，或紧跟在另一个运算符之后，则必然无解。

把每个二元运算的左操作数外层括号规范化地去掉后，每个合法表达式与一种括号过程一一对应：遇到运算符新开一个尚未闭合的结构，遇到数字时可以闭合任意多个已有结构。

做法

子任务 1 使用区间动态规划，枚举根是一元符号还是某个二元运算符，复杂度 $O(n^3)$。

中档算法在压缩记号串上设 $f[i][j]$ 为处理前 $i$ 个记号、仍有 $j$ 个结构未闭合的方案数。遇到运算符时只能令未闭合数加一；遇到数字时枚举从原状态闭合多少个结构，直接求和为 $O(m^3)$。

满分算法注意到数字转移为

对上一行做后缀和即可把每次数字转移降为 $O(m)$。最终答案是 $f[m][0]$。

正确性说明

连续数字在任何 UAE 中都必须属于同一个整数叶子，因此压缩数字段不会改变表达式数量。若乘号或除号位于开头，或其左侧紧邻运算符，它既不能成为一元运算符，也没有合法左操作数，所以此时答案确为零。

对其余记号串，每个运算符都对应新开的一个表达式结构；读到数字叶子时，可以依次闭合任意数量的待闭合结构。规范地去掉二元运算左操作数最外层括号后，这一过程与原 UAE 一一对应。于是 $f[i][j]$ 完整且不重不漏地计数处理前 $i$ 个记号后仍有 $j$ 个待闭合结构的方案，数字处的所有合法前态恰为 $k\ge j$，从而得到后缀和转移。全部记号处理完后只有 $j=0$ 表示完整表达式，所以答案为 $f[m][0]$。

复杂度

满分算法时间复杂度为 $O(m^2)$，空间复杂度为 $O(m)$，其中 $m\le |s|$ 是压缩后的记号数。