OI中的数学

2018-08-22 10:46:37


数学这个东西,在OI中虽然不常常会考,但是,有些时候它能大大减少代码量,还有的时候某些出题人丧心病狂地就是要出数论题,这时候,掌握一些数论知识便是必要的。


Catalan(卡塔兰数)

卡塔兰数,又称卡特兰数,用图片画出来就像这样:

Catalan Number

在那条红色线上的就是卡塔兰数。

或者画成这样: Catalan2

最下面一排的值表示从(0,0)点到这个点有多少种走法,即卡塔兰数。

通过图2,可以发现卡塔兰数可以转变为以下问题:

有N个A和N个B,现在要求对它们进行排列,但是从第1个位置到第2N个位置,B的个数不能超过A的个数。
问合法排列有几种?

(A相当于向上的边,B相当于向下的边,答案为Catalan(N))

那么卡塔兰数的通项公式怎么求呢?

大不了开个二维数组直接模拟图1

证明稍有些繁琐,可能大家都不愿意看,所以直接上定义公式:

或者组合公式(证明

公式是 $ C_{2n}^{n} /(n+1) $

$ C_{2n}^{n} - C_{2n}^{n-1}$

在OI中,因为卡塔兰数增长极快,所以要用高精度。

卡塔兰数例题:

球迷购票问题 (解析:50元球票相当于元素A,100元球票相当于元素B,在任意时刻B的数量不能超过A,即为Catalan)

(解析:入栈相当于元素A,出栈相当于元素B,在任意时刻出栈次数不能超过入栈次数,答案为Catalan数)