我永远喜欢小圆！ | 【解题报告】P11588 [KTSC 2022 R2] 彩色括号序列
Starrykiller
·
·
题解
鲜花：
约定：\texttt{1-indexed}。
这题也太困难了吧！
首先你得有一个靠谱的 \mathrm{poly} 复杂度的做法。
括号序列的一个经典思路是，拆第一对匹配的括号 DP，形如 \texttt{\textcolor{red}(...\textcolor{red})...}。
由此可以设计出状态：
判掉 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 单独匹配的贡献）：
\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。
这个东西一眼就很可以优化。考虑怎么优化到三次方。
\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 里面了，所以可以直接丢掉。那么就是
\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