自动搬运

查看原文

来自洛谷，原作者为

	Starrykiller 祈祷着今后的你的人生，永远都有幸福的「魔法」相伴。

搬运于2025-08-24 23:08:37，当前版本为作者最后更新于2025-04-05 22:09:43，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

鲜花：

---

约定：$\texttt{1-indexed}$。

---

这题也太困难了吧！

首先你得有一个靠谱的 $\mathrm{poly}$ 复杂度的做法。

括号序列的一个经典思路是，拆第一对匹配的括号 DP，形如 $\texttt{\textcolor{red}(...\textcolor{red})...}$。

由此可以设计出状态：

• $f(l,r)$：钦定 $l,r$ 被选中且匹配的合法本质不同子序列个数。
• $g(l,r)$：钦定 $l,r$ 被选中（但未必匹配）的合法本质不同子序列个数。

判掉 Corner Case：

• 若 $A_l\gt 0$ 或 $A_r\lt 0$，则 $f(l,r)=g(l,r)=0$。
• 若 $|A_l|=|A_r|$，则 $f(l,r)=0$。

考虑转移。

首先 $f(l,r)$ 的转移是容易的——无非就是某个 $g$ 外面套一层 $\texttt{()}$，但是我们要保证不重不漏地转移。

观察到关键性质：令 $L\lt l\lt r\lt R$，且 $A_L=A_l$，$A_r=A_R$。那么，$g(l,r)$ 这个状态代表的括号序列一定被 $g(L,R)$ 代表的括号序列包含——这意味着我们直接计数 $g(L,R)$ 即可。

$\gdef \pre {\operatorname{pre}}$ $\gdef \nxt {\operatorname{nxt}}$

为了方便描述，令 $\pre(i)$ 表示 $i$ 前面第一个满足 $A_i=A_j$ 的 $j$（不存在规定为 $0$），$\nxt(i)$ 同理（不存在规定为 $(n+1)$）。

那么我们可以得到 $f$ 的转移（别忘了算上 $l,r$ 单独匹配的贡献）：

$$f(l,r)=1+\sum_{ \substack{ l\lt i\lt j\lt r \\ \pre(i)\lt l,A_l\neq A_i\\ \nxt(j)\gt r,A_j\neq A_r } } g(i,j) $$

考虑 $g$ 的转移。显然 $g$ 蕴含 $f$，然后枚举 $l$ 匹配右括号 $i$，以及 $i$ 后面的第一个左括号 $j$。

显然我们还是要贪心地选取最前面的 $j$，所以 $\pre(j)\lt i$。朴素地考虑可以得到：

$$g(l,r)=f(l,r)+\sum_{ \substack{ l\lt i\lt j\lt r \\ |A_l|\neq |A_i|,A_i\gt 0 \\ A_j\lt 0, |A_i|\neq |A_j|\\ \pre(j)\lt i } } f(l,i)\cdot g(j,r) $$

这对吗？这显然不对。我们只考虑了 $j$，但是 $i$ 同样被算重了。

一个朴素的想法是，加入限制 $\nxt(i)\gt j$（贪心地取最右边的 $i$）。这对吗？

这还是不对。考虑如下的事情：

$$\begin{aligned} \mathop{\texttt{\textcolor{ff99cc}(}}\limits_{l} \texttt{...} \mathop{\texttt{\textcolor{935ba5})}}\limits_{i} \texttt{...} \mathop{\texttt{\textcolor{87b3ed}(}}\limits_{j} \texttt{...} \mathop{\texttt{\textcolor{935ba5})}}\limits_{i'} \texttt{...} \mathop{\texttt{\textcolor{87b3ed}(}}\limits_{j'} \texttt{...} \texttt{\textcolor{F4DE90})} \texttt{\textcolor{FF8C69}(} \mathop{\texttt{\textcolor{eb234b})}}\limits_{r} \end{aligned} $$

考虑 $f(l,i)\cdot g(j,r)$，$f(l,i')\cdot g(j',r)$，这样还是算重了。

考虑算重的是哪个部分：显然是 $f(l,i)\cdot g(j',r)$。我们直接减去它即可。不难发现这样也不需要再加入 $\nxt(i)\gt j$ 的限制，我们直接减去 $[\pre(i)\gt l] f(l,\pre(i))\cdot g(j,r)$ 即可。

于是得到转移式

$$g(l,r)=f(l,r)+\sum_{ \substack{ l\lt i\lt j\lt r \\ |A_l|\neq |A_i|,A_i\gt 0 \\ A_j\lt 0, |A_i|\neq |A_j|\\ \pre(j)\lt i } } f(l,i)\cdot g(j,r) - \sum_{ \substack{ l\lt i\lt j\lt r \\ |A_l|\neq |A_i|,A_i\gt 0 \\ A_j\lt 0, |A_i|\neq |A_j|\\ \pre(j)\lt i \\ \pre(i)\gt l } } f(l,\pre(i))\cdot g(j,r) $$

答案就是所有 $\pre(i)=0,\nxt(j)=n+1$ 的 $g(i,j)$ 之和。

暴力地转移，时间复杂度 $\mathcal{O}(n^4)$。由于状态数极少，所以记忆化搜索可以通过子任务 $1\sim 4$，期望得分 $76$。

---

这个东西一眼就很可以优化。考虑怎么优化到三次方。

$$f(l,r)=1+\sum_{ \substack{ l\lt i\lt j\lt r \\ \pre(i)\lt l,A_l\neq A_i\\ \nxt(j)\gt r,A_j\neq A_r } } g(i,j) $$

首先你发现 $A_l\neq A_i$ 这个条件已经蕴含在 $\pre(i)\lt l$ 里面了，所以可以直接丢掉。那么就是

$$f(l,r)=1+\sum_{ \substack{ l\lt i\lt j\lt r \\ \pre(i)\lt l, \nxt(j)\gt r } } g(i,j) $$

考虑对每一个 $g(i,j)$，把它贡献到 $f(l,r)$。不难发现它只会贡献到 $l\in (\pre(i),i),r\in(j,\nxt(j))$（开区间）这个矩形中。同一个长度之间没有贡献，所以直接做 $\Theta(n)$ 次二维前缀和即可，这是 $\Theta(n^3)$ 的；

$$g(l,r)=f(l,r)+\sum_{ \substack{ l\lt i\lt j\lt r \\ |A_l|\neq |A_i|,A_i\gt 0 \\ A_j\lt 0, |A_i|\neq |A_j|\\ \pre(j)\lt i } } f(l,i)\cdot g(j,r) - \sum_{ \substack{ l\lt i\lt j\lt r \\ |A_l|\neq |A_i|,A_i\gt 0 \\ A_j\lt 0, |A_i|\neq |A_j|\\ \pre(j)\lt i \\ \pre(i)\gt l } } f(l,\pre(i))\cdot g(j,r) $$

再来看这个，枚举 $i$，求出合法的 $j$ 之和，这是容易的（对于 $|A_i|\neq |A_j|$ 的限制可以直接容斥掉）。

综上时间复杂度 $\Theta(n^3)$。精细实现可以通过本题。代码是简单的。

小圆亲亲！/qq