Anton and School - 2题解

发布时间 2023-09-26 18:07:32作者: OIerBoy

2023-09-26

题目

难度&重要性(1~10):

题目来源

luogu

题目算法

组合数学

解题思路

前置知识

范德蒙德卷积公式:\(\sum\limits_{i=0}^kC_{n}^{i}\times C_{m}^{k-i}=C_{n+m}^k\)

至于证明请看此篇文章

Sol

我们这道题很明显就要从 \(\begin{matrix}\underbrace{(((\cdots (((}\\k\end{matrix} \begin{matrix}\underbrace{)))\cdots )))}\\k\end{matrix}\) 这里入手,不然的话题目完全可以叫你保证括号合法就行了。

这样我们就可以发现序列的前后是不会互相影响的,即可以独立的计算贡献,而为了保证不去重复计算答案,我们只需要去考虑计算左括号的贡献就行了。

当前位置为 ( 时,定它作为最右边的左括号,记左边有 \(a\) 个左括号,右边有 \(b\) 个右括号,则当前对答案的贡献为:\(\sum\limits_{i=0}^{\min(a-1,b-1)}C_{a-1}^i\times C_{b}^{i+1}\)。但只是这个式子不足以让我们通过这道题,时间复杂度是 \(O(n^2)\) 的。

这时,我们就需要用到上面的范德蒙德卷积公式了。

\[\sum\limits_{i=0}^kC_{n}^{i}\times C_{m}^{k-i}=C_{n+m}^k \]

可以发现我们推出来的式子很像范德蒙德卷积公式,这样我们就可以对式子进行化简了。

\[\begin{aligned}& \sum\limits_{i=0}^{\min(a-1,b-1)}C_{a-1}^i\times C_{b}^{i+1}\\ =& \sum\limits_{i=0}^{\min(a-1,b-1)}C_{a-1}^{a-1-i}\times C_{b}^{i+1}\\ = & C_{a+b-1}^a\end{aligned} \]

这样我们只需要预处理一下 \(1\sim i\) 出现过的左括号记为 \(l_i\)\(i\sim n\) 出现过的右括号记为 \(r_i\) 就可以了。

完成状态

已完成