题解 P1722 【矩阵 II】与 卡特兰数(Catalan)

这题是卡特兰数的一道裸题。

利用这一道题介绍一下什么是卡特兰数(Catalan)

卡特兰数的定义式:

\( h_n=\left\{\begin{matrix} 1 & n=1,0 \\ \sum_{k=1}^{n-1}h_kh_{n-k}& n> 1 \end{matrix}\right. \)

由于这个定义式太复杂。平时我们很难用到。

卡特兰数的推出式:

常见的有下面两种:

  • \(\frac{1}{n+1}\textrm{C}_{2n}^{n}\)

  • \(H_{n+1}=\frac{4n+2}{n+2}H_{n}\)
    \(H_{n}=\frac{4n-2}{n+1}H_{n-1}\)

公式一为通项公式。公式二位递推公式。

关于公式一的证明,由于题主的水平有限,再加之以证明过程对于信息竞赛来说意义不大。此处感兴趣的小伙伴可以自行BFS。(思路是利用母函数与二项式定理)

公式二证明:

数学思想:把阶乘拆开,然后配方。

过程如下:

\[\begin{aligned} h_{n+1}&=\frac{1}{n+2}\textrm{C}_{2n+2}^{n+1} \\ &=\frac{1}{n+2}\frac{\left ( 2n+2 \right )!}{\left ( n+1 \right )!\times\left ( n+1 \right )!}\\ &=\frac{1}{n+2}\frac{\left ( 2n \right )!\times\left ( 2n+1 \right )\left ( 2n+2 \right )}{n!\times n! \times \left ( n+1 \right )^2}\\ &=\frac{1}{n+2}\frac{\left ( 2n+1 \right )\left ( 2n+2 \right )}{n+1}\times\frac{1}{n+1}\textrm{C}_{2n}^{n}\\ &=\frac{4n+2}{n+2}h_n \end{aligned} \]

另一个公式类似,读者自证。

卡特兰数的应用:

  • 出栈次序
  • n对括号正确匹配数目
  • 给定节点组成二叉搜索树
  • 在圆上选择2n个点,将这些点成对连接起来使得所得到的n条线段不相交的方法数
  • 求一个凸多边形区域划分成三角形区域的方法数

(这里建议记住卡特兰数的前几项:1, 1, 2, 5, 14, 42, 132, 429, 1430...)

关于此题:

这道题虽然说是卡特兰数裸题,但有一个细节,就是答案对100取模。

嗯。。然后,题主就写了一个错误的写法。

像这样:

void catalan(int n)
{
	f[0]=f[1]=1;
	for(int i=1;i<=2*n;++i)
	{
		f[i]=(f[i-1]*(4*i-2)/(i+1));
		f[i]=f[i]%100;	//这里是错误点
	}
}

为了防止溢出,我甚至开了 unsigned long long....

错误的原因:模运算与基本四则运算有些相似,但是除法例外。其规则如下

  • \((a+b)\%p\) \(=\) $ ( a%p + b%p )$ \(\%p\)
  • \((a-b)\%p\) \(=\) $ ( a%p - b%p )$ \(\%p\)
  • \((a\times b)\%p\) \(=\) $ ( a%p \times b%p )$ \(\%p\)
  • \((a^b)\%p\) \(=\) $ (( a%p )^b)$ \(\%p\)

故这道题不适合用上文中的递推式来做。而应该用卡特兰数的定义式来做。虽然它不常用

代码如下:

#include <bits/stdc++.h>
#define MAXN 1000
long long f[MAXN];
int main()
{
	int n;
	std::scanf("%d",&n);
	f[0]=f[1]=1;
	for(int i=2;i<=n;++i)
		for(int j=1;j<=i;++j)
		{
			f[i]+=f[j-1]*f[i-j];
			f[i]%=100;
		}
	std::printf("%d",f[n]);
	return 0;
}
上一篇:数据结构与算法笔记(一) 数据结构与算法绪论


下一篇:LOJ6160 二分图染色