0%

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

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

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