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\) 就可以了。
完成状态
已完成