【7】卡特兰数学习笔记

技术分享 8个月前 (07-12) 0 999+

关注

前言

感觉卡特兰数是非常实用的小技巧，一般在题目中以经典模型或发现递推式相同从而运用。就是典型的会的人秒掉，不会的人死都想不出来。

卡特兰数

定义

对于一个由 (n) 个 (+1) 和 (n) 个 (-1) 组成的序列，满足每个位置的前缀和 (ge 0) 的不同的序列数称为 (text{Cat}_{n})，表示卡特兰数的第 (n) 项。

务必熟知这个概念，这个概念可以转化为以下三个经典问题。

(1)：由 (n) 对括号组成的不同的括号序列的数量为 (text{Cat}_{n})。

(2)：一个栈进栈序列 (1,2,3dots,n) 的有 (text{Cat}_{n}) 种不同的出栈序列。

(3)：大小为 (ntimes n) 的方格图，起点为 ((0,0))，终点为 ((n,n))。每次只能向右或向上走一步，不能经过直线 (y=x+1) 上的点，合法路径数为 (text{Cat}_{n})。

递推式

边界情况为 (text{Cat}_{0}=1)。

卡特兰数的递推式 (1) 为 (text{Cat}_{n}=sum_{i=1}^ntext{Cat}_{i-1}times text{Cat}_{n-i})。

考虑问题 (2) 的另一种解法，设 (f[n]) 表示前 (n) 个元素不同的出栈序列的数量。转移的话考虑枚举 (n) 是第 (i) 个出栈的元素，则前 (i) 个元素和后 (i) 个元素出栈顺序独立，由乘法原理得这种情况的方案数为 (f[i-1]times f[n-i])。最后由加法原理把不同的 (i) 的方案数加起来。

因此，有 (text{Cat}_{n}=sum_{i=1}^ntext{Cat}_{i-1}times text{Cat}_{n-i})。

卡特兰数的递推式 (2) 为 (text{Cat}_{n}=text{Cat}_{n-1}timesfrac{4n-2}{n+1})。

我们利用卡特兰数的通项公式(见下一板块)，直接带入通项公式就可以证明。

[begin{aligned} text{Cat}_n &= C_{2n}^n-C_{2n}^{n+1} \ &= frac{(2n)!}{(2n-n)!(n)!}-frac{(2n)!}{(2n-n-1)!(n+1)!}\ &= frac{(2n)!}{(n)!^2}-frac{(2n)!}{(n)!^2frac{n+1}{n}}\ &= frac{(2n)!}{n!^2(n+1)}\ end{aligned}]

将 (n) 用 (n-1) 代换后相除得到递推系数。

[text{Cat}_{n-1}=frac{(2n-2)!}{(n-1)!^2n} ]

[begin{aligned} frac{text{Cat}_n}{text{Cat}_{n-1}}&=frac{frac{(2n)!}{(n)!^2(n+1)}}{frac{(2n-2)!}{(n-1)!^2n}}\ &=frac{(n-1)!^2n(2n)!}{n!^2(n+1)(2n-2)!}\ &=frac{ntimes 2n(2n-1)}{n^2(n+1)}\ &=frac{4n-2}{n+1} end{aligned}]

因此，有 (text{Cat}_{n}=text{Cat}_{n-1}timesfrac{4n-2}{n+1})。

由递推式相同，我们还可以推出卡特兰数可以转化为这三个经典问题。

(4)：由 (n) 个节点可以构成 (text{Cat}_{n}) 棵不同的二叉树。

(5)：在圆中选择 (n) 个点对，使这些点对连成的 (n) 条线段互不相交的方案数为 (text{Cat}_{n})。

(6)：对角线不相交的情况下，将一个凸多边形区域分成三角形区域的方法数为 (text{Cat}_{n})。

通项公式

卡特兰数的通项公式为 (text{Cat}_{n}=C_{2n}^n-C_{2n}^{n+1})，其中 (C) 为组合数。

考虑问题 (3) 的另一种解法，显然，考虑分配向上和向右的一步的位置，从 ((x,y)) 走到 ((n,n)) 只能向右或向上的路径数为 (C_{n-x}^{n-y})。

使用反射容斥，不合法的路径的方案数等价于从 ((-1,1)) 到 ((n,n)) 的方案数。因为如果碰到直线 (y=x+1) 上的点，就把从起点到这个碰到的点的路径沿 (y=x+1) 翻折。显然不合法路径和从 ((-1,1)) 到 ((n,n)) 的路径一一对应，形成双射。不合法路径的数量即为 (C_{2n}^{n+1})。

因此，有 (text{Cat}_{n}=C_{2n}^n-C_{2n}^{n+1})。

例题

例题 (1) ：

P2532 [AHOI2012] 树屋阶梯

首先每一列最上面的那些木块任意两个不能被包含在同一个长方形中，而这样的木块有 (n) 个，长方形也只有 (n) 个，因此每个长方形右上角必然为某一列最上面的木块。

直接求做不了，考虑递推。设 (f[n]) 为 (n) 级阶梯的方案数，枚举最后一个长方形的右上角，把图分成了左上角的阶梯和右下角的阶梯。这两个阶梯是完全相同且独立的子问题，可以直接乘法原理合并得出转移式。

[f[n]=sum_{i=1}^n f[n-i]f[i-1] ]

发现这就是卡特兰数的递推式 (1)，使用卡特兰数的递推式 (2) 加上高精度就做完了。

#include <bits/stdc++.h> using namespace std; int n,ans[600000]; void mul(int x) { 	int flag=0; 	for(int i=1;i<=50000;i++)ans[i]=ans[i]*x+flag,flag=ans[i]/10,ans[i]%=10; }  void div(int x) { 	int flag=0; 	for(int i=50000;i>=1;i--)ans[i]+=flag*10,flag=ans[i]%x,ans[i]=ans[i]/x; }  int main() { 	scanf("%d",&n); 	ans[1]=1; 	for(int i=2;i<=n;i++)mul(4*i-2),div(i+1); 	bool flag=0; 	for(int i=50000;i>=1;i--) 	    if(flag||ans[i])printf("%d",ans[i]),flag=1; 	return 0; }

小技巧：熟记卡特兰数前几项 (1,1,2,5,14,42,132dots)，看到第 (3) 项为 (5) 直接猜卡特兰数，写一发过了，证明确实是卡特兰数。

例题 (2) ：

P3200 [HNOI2009] 有趣的数列

由于奇数项和偶数项又分开的限制，所以我们从小到大考虑每个数是填在奇数项的第一个可用的位置还是偶数项的第一个可用的位置。

如果已经填入的偶数项的数大于奇数项的数，假设奇数项填到了 (2k-1)，因为至少多一项，那偶数项至少填到了 (2k+2)。由于从小到大填，则下一个奇数项 (2k+1) 必然大于 (2k+2) 的数，与条件 (3) 奇数项小于偶数项矛盾。

因此，我们可以把填在奇数项看作左括号，填在偶数项看作右括号，就转化为了合法括号序列计数问题，答案就是卡特兰数。

由于模数不一定是质数，逆元不一定存在，所以我们选用递推式 (2) 加分解质因数求最终答案。

#include <bits/stdc++.h> using namespace std; int n,mod,ans=1,pr[500000],dm[5000000],cnt=0; bool b[5000000]; map<int,int>p; int power(int a,int p) { 	int x=a,ans=1; 	while(p) 	   { 	   	if(p&1)ans=1ll*ans*x%mod; 	   	p>>=1; 	   	x=1ll*x*x%mod; 	   } 	return ans; }  void init(int mx) { 	b[1]=1; 	for(int i=2;i<=mx;i++) 	    { 	    if(!b[i])pr[++cnt]=i,dm[i]=i;        	for(int j=1;j<=cnt&&i*pr[j]<=mx;j++)        	    { 		    b[i*pr[j]]=1,dm[i*pr[j]]=pr[j]; 		    if(i%pr[j]==0)break;        	    }         	} }  void insert(int x) { 	while(x!=1)p[dm[x]]++,x/=dm[x]; }  void outsert(int x) { 	while(x!=1)p[dm[x]]--,x/=dm[x]; }  int main() { 	init(4000000); 	scanf("%d%d",&n,&mod); 	for(int i=1;i<=n;i++)insert(i*4-2),outsert(i+1); 	auto it=p.begin(); 	while(it!=p.end()) 	   { 	   if((*it).second)ans=1ll*ans*power((*it).first,(*it).second)%mod; 	   it++;        } 	printf("%dn",ans); 	return 0; }

例题 (3) ：

CF2063F2 Counting Is Not Fun (Hard Version)

看到括号问题，直接想到卡特兰数。如果没有已经固定的括号，那答案就是 (text{Cat}_n)。

我们进一步观察，即使括号序列中已经存在若干个连续的位置构成合法括号序列，只要剩余的位置数为 (2n)，答案一定就是 (text{Cat}_n)。因为合法的括号序列不会对接下来的填法造成任何影响，所以可以忽略。

现在我们考虑转化出没有已经固定的括号的情况。考虑离线，对最终确定的括号序列建出一棵括号树。由括号树的性质，想计算某个节点的空余位置大小只需要减去其直接子节点的位置大小。这样一定可以计算到所有的空余区域，且由于不同节点之间的空余区域独立，直接乘法原理合并答案。

因此，我们每个节点维护其对应的区间大小与子节点区间大小的和。更新一个节点时，就先撤销它对总方案的贡献，修改后再加回来。

但正着加可能会导致加入一个节点后大量节点父节点改变很难计算，所以考虑倒着删边。这样我们就可以使用并查集维护一个结点的父亲，删除时只需要撤销贡献，然后合并自己和父节点即可。注意合并的方向有影响，必须是儿子合并到父亲。

代码中在 (0) 和 (n+1) 处添加了一对虚拟括号来保证括号树不是森林，同时避免一些边界情况。

#include <bits/stdc++.h> using namespace std; long long t,n,cat[800000],inv[800000],p[800000],v[800000],l[800000],r[800000],f[800000],fa[800000],ans[800000],st[800000],top=0,now=1; char a[800000]; const long long mod=998244353; long long power(long long a,long long p) { 	long long x=a,ans=1; 	while(p) 	   { 	   	if(p&1)ans=ans*x%mod; 	   	p>>=1; 	   	x=x*x%mod; 	   } 	return ans; }  long long getf(long long x) { 	if(fa[x]==x)return x; 	else return fa[x]=getf(fa[x]); }  void merge(long long x,long long y) { 	long long p=getf(x),q=getf(y); 	if(p!=q)v[p]+=v[q],fa[q]=p; }  int main() { 	cat[0]=cat[1]=inv[0]=inv[1]=1; 	for(int i=2;i<=300000;i++)cat[i]=cat[i-1]*(4*i-2)%mod*power(i+1,mod-2)%mod; 	for(int i=2;i<=300000;i++)inv[i]=power(cat[i],mod-2); 	scanf("%lld",&t); 	while(t--) 	   { 	   	scanf("%lld",&n); 	   	for(int i=0;i<=n;i++)p[i]=v[i]=0,fa[i]=i,now=1; 	   	a[0]='(',l[0]=0,r[0]=2*n+1; 	   	for(int i=1;i<=n;i++)scanf("%lld%lld",&l[i],&r[i]),a[l[i]]='(',a[r[i]]=')',p[l[i]]=i; 	   	for(int i=0;i<=2*n;i++) 	   	    if(a[i]=='(')st[++top]=p[i]; 	   	    else v[st[top-1]]+=(r[st[top]]-l[st[top]]+1),f[st[top]]=st[top-1],top--; 	   	for(int i=0;i<=n;i++)now=now*cat[(r[i]-l[i]-1-v[i])>>1]%mod; 	   	ans[n+1]=now; 	   	for(int i=n;i>=1;i--) 	   	    { 	   	    	now=now*inv[(r[i]-l[i]-1-v[i])>>1]%mod; 	   	    	now=now*inv[(r[getf(f[i])]-l[getf(f[i])]-1-v[getf(f[i])])>>1]%mod; 	   	    	v[getf(f[i])]-=(r[i]-l[i]+1),merge(f[i],i); 	   	    	now=now*cat[(r[getf(f[i])]-l[getf(f[i])]-1-v[getf(f[i])])>>1]%mod; 	   	    	ans[i]=now; 			} 		for(int i=1;i<=n+1;i++)printf("%lld ",ans[i]); 		printf("n"); 	   } 	return 0; }