Expression

HDU2015。

有 $n$ 个数和 $n-1$ 的运算符。

每一次操作你可以选择相邻的两个数并将他们按照他们之间的运算符进行运算。

显然 $n-1$ 次运算后这些数会变为一个。

求按每一种操作顺序操作之后，最终的数的和。对 $10^9+7$ 取模。

$n\le 500$。

显然有一个 $\mathcal{O}(n^2)$ 的区间 DP：令 $f_{i,j}$ 表示区间 $[i,j]$ 的答案，那么有：

$$f_{i,j}=\sum_{i\le k<j}\operatorname{opt}(f_{i,k},f_{k+1,j})$$

然后你就发现你 WA 了。

原因是这样的：$f$ 计算的是和。

举一个例子：不妨设 $f_{i,k}$ 里面的所有数是 $\{1,2,3\}$，运算符是 $+$，$f_{k+1,j}$ 里面的所有数是 $\{1,4,5\}$，那么 $f_{i,k}$ 和 $f_{k+1,j}$ 要是直接求和的话会得到 $16$ 的结果。但是很显然答案集合应该是 $\{1+1,1+4,1+5,2+1,2+4,2+5,3+1,3+4,3+5\}$，和显然不是 $16$。

于是我们发现，$f_{i,k}$ 里面的每一个数都会在累加过程中被累加 $(j-k)!$ 次（即区间 $[k+1,j]$ 的长度的阶乘，也可以说是右边集合里的元素个数）；同理，$f_{k+1,j}$ 中的每一个数字都会被累加 $(k-i+1)!$ 次。

减法和乘法同理。

于是我们得出结论：

$$\operatorname{op}(f_{i,k},f_{k+1,j})=\begin{cases}(j-k)!f_{i,k}+(k-i+1)!f_{k+1,j} & \text{op=+}\\ (j-k)!f_{i,k}-(k-i+1)!f_{k+1,j} & \text{op=-}\\ f_{i,k}f_{k+1,j} & \text{op}=\times \end{cases}$$

然后你又 WA 了。

原因是，对于 $[i,k]$ 和 $[k+1,j]$，我们只是钦定最后一个操作必须是连接这两个区间的操作，并没有限定这两个区间内部应该怎么操作。也就是说，我们并没有确定这两个区间如何交叉的操作。

设左边的区间有 $len_1$ 个符号，右边有 $len_2$ 个。那么根据简单组合计数，有 $\binom{len_1+len_2}{len_1}$ 种他们交叉放置的方案（注意这里我们假设已经钦定了左右区间内部的顺序已经确定）。

那么问题就解决了，只需要将交叉的方案与之前的错误 $\operatorname{op}$ 相乘即可。

$$\frac{1}{\binom{len_1+len_2}{len_1}}\operatorname{op}(f_{i,k},f_{k+1,j})=\begin{cases}(j-k)!f_{i,k}+(k-i+1)!f_{k+1,j} & \text{op=+}\\ (j-k)!f_{i,k}-(k-i+1)!f_{k+1,j} & \text{op=-}\\ f_{i,k}f_{k+1,j} & \text{op}=\times \end{cases}$$

然后大力区间 DP 即可。