UyHiP-2013-Nov

前几个月的 UyHiP 连题解都没看……

Problem

定义一个括号序列的值为：所有括号对的深度的积。例如 ((())()) 的值为 3*2*2*1 = 12 。

求所有 \(n\) 个括号的括号序列的权值和。要求给出一个 closed-form 。

Solution

下个月再发？

其实非常简单啦。

答案非常简单，但是求一个简单的解释。

我是直接分析 dp 。首先这个题有个非常简单的 dp ： \(f_{i, j}\) 表示 \(i\) 个字符深度为 \(j\) 的积的总和。打出来后发现是有规律的……于是数学归纳法就好。

Brand 给了一个特别漂亮的解释。对于一个合法的串 S ，假设是 (()()) 吧，我们在其左边插入一个 ( ，再在其它任意一个位置插入 ) ，可以得到

• ()(()())
• (()()())
• ((())())
• ((()()))
• ((()()))
• ((()()))

注意每个串可以由很多种方式得到，而方案数恰好就是这个序列的权值。每次的 ) 插入方案数为 \(2n + 1\) ，所以总方案数 \(\prod_{i=0}^{n-1} (2i + 1)\)

某盾曰：这肯定是出题人在算 Catalan 的时候算错了然后发现是这么个东西再出出来的！

nonsense

考试后谈论分数什么的毫无意义吧。

他要考得好我就不开心，我要考得好他就不开心。总会有人不开心，何必戳破这层纸呢。