《卡特兰数》学习总结

daduoli · 2023-12-06 21:08:39 · 个人记录

貌似不是很有用的一个东西。

这是我觉得讲的最好的一篇文章

定义

这个东西光定义就有好几种，并且每种定义都有一定的运用。

递归定义： f_n=\sum\limits_{i=0}^{n-1} f_i\times f_{n-i-1}
递推关系： f_n=f_{n-1}\times \frac {(4n-2)}{n+1}
通项公式： \frac 1{n+1}C_{2n}^n=C_{2n}^n-C_{2n}^{n+1}

递推关系怎么来的不太知道，从上面化简应该可以得到，不过不需要特别注意就是了。

递推定义解释

至于递归定义是怎么来的 Serror 给了我一个绝妙的解释。

因为 f_i 表示有 i 对括号串的方案，如果直接枚举一个 i ，表示分成两部分，一部分是 i ，另一部分是 n-i，方案数是 f_{i}\times f_{n-i} 就可能会出现算重，倘若在外面直接先对于左边部分整体用一个括号括起来，那么就一定不会算重了。

大概长成上面这个样子。

通项公式解释

考虑一个关于卡特兰数最基本的问题，我们现在要从 1,1 走到 n,n ，那么，然后我们要保证不碰到 y=x+1 的这一条直线

如果直接正着求，发现妃常难求，考虑求他的补集，求非法的走法的方案。

那么我们定义第一次碰到直线的位置为 (z,z+1) 。

那么我们考虑从这个位置之后的路径我们都沿着 y=x+1 进行翻折。

考虑黑色为原本的路径，橙色为翻折过后的路径，这样实际上我们发现只要经过翻折之后，路径的终点一定都是 (n-1,n+1) ，这个是容易发现的。

因为向右的边还剩 n-z 条，向上的边还剩 n-1-z 条，如果翻转之后，就相当于少走了一条向右的边，多走了一条向上的边。

然后我们有结论，从 1,1\to (n-1,n+1) 的所有路径一定不重不漏的对应所有非法路径。

相当于每条路径都是一一映射过去的。

所有总方案数就是 C(2n,n)-C(2n,n+1) （以 0,0 为起点时，是这个公式，上面写的时候搞错了，不过问题不大，差不都）

一个小小的拓展，如果要去 n,m 呢？

同理，我们终点是 (n,m) ，那么不合法路径的终点都是 (m-1,n+1)

方案就是 C_{n+m}^n-C_{n+m}^{n+1}

应用

括号匹配

合法括号匹配串的数量，恰好 n 对括号串。

实际上将左括号看做向右，右括号看做向上同理。

然后一样做掉就可以了。

不相交弦问题

这里使用了 Morning-Glory 的图片

我们将最上面的点看成起点，将逆时针方向看做正方向。

将匹配的起点看做左括号，终点看做右括号，容易发现所有前缀和中左括号的数量大于等于右括号的数量。

所以又是卡特兰数问题了。

二叉树个数

有 n 个点，问能构成多少不同的二叉树

容易得到 f_n=\sum\limits_{i=0}^n f_i\times f_{n-i-1} 。

容易发现这和卡特兰数的递归定义一样，所以实际上这个东西就是卡特兰数。

凸多边形三角划分问题

和上面不相交弦感觉貌似很像，其实。

我们在凸多边形中随便挑两个顶点连一条边，这个凸多边形就会被分成两个小凸多边形，由于每条直线不能相交，接下来我们就只要求这两个小凸多边形的划分方案然后乘起来即可

和二叉树的构成问题一样，我们枚举大凸多边形被分成的两个小凸多边形的大小即可

实战演练

P1375 小猫

容易发现这是不相交弦问题，直接上卡特兰数就行了。

P1754 球迷购票问题

典中典，相当于任意时刻 50 元的人数要大于等于 100 元的人数就行了。

不过这里不能用组合数，会爆掉，只能用递推公式。

P3200 [HNOI2009] 有趣的数列

随便口胡一下。

容易发现对于一个 2k 位置，他一定比 1\le i<2k 位置上的所有数都要大。

所以填在 2k 位置的数一定要 \ge 2k 。

然后考虑转换题意，考虑从 1\to 2n 填数，每次要么填在偶数中最小的位置，要么填在奇数中最小的位置。

有一个结论，任意时刻，奇数数量大于等于偶数数量。

然后这个就是卡特兰数没什么好说的了。

不过模数不一定是质数要对所有数进行分解质因数，这里有一个 O(n) 分解连续一段质因数的 trick ，直接看代码应该就能懂。

for(int i=n*2;i>1;--i) {
    if(mins[i]<i) {
        sum[mins[i]]+=sum[i];
        sum[i/mins[i]]+=sum[i];
    }
}

其中 mins_i 为 i 最小的质因子。

上面的说完了，还有一个很严重的问题，结论怎么证明。

具体证明如果存在某一时刻偶数个数大于奇数，那么我们考虑此事填了 2k+1 个数，那么偶数有 k+1 个，奇数有 k 个。（一定会出现偶数恰好比奇数多一的情况）

那么我们考虑偶数的下一个位置可以填什么，如果偶数想放在 k+1 这个位置，那么他至少得是 2k+2 ，但是我们才填到 2k+1 ，哪来的 2k+2 给我们填，所以一定不合法。

然后对于其他情况都会发现严格满足题目限制（其实就是我菜，不会证），于是证毕。

P7118 Galgame

首先可以直接统计的是长度小于我们当前序列的，对于大小为某一个值的二叉树的个数就是卡特兰数。

接着对于每个节点，考虑它的左节点，即另一棵树的左节点的数量一定小于当前树最节点数量就可以统计答案。

具体的，统计一下，枚举左子树的大小。

for(int i=0;i<sz[l[u]];++i) {
    (ans+=xs*ctl[i]%P*ctl[sz[u]-1-i]%P)%=P;
}

然后考虑大小相等的情况，要么往左边递归（左边又不痛的地方），要么往右边递归（说明左边完全相同，不同的地方在右边），所以递归左边的时候要再乘上右边可能的方案数，即 ctl[sz[r[u]]] ，递归右边因为要保证左边完全相同所有不用管。

但是这样复杂度是 O(n^2) 的。

有一个比较厉害的优化。

我们不仅可以枚举左子树，也可以枚举右子树减去不合法的，具体的，用全集减去一定不合法的。

然后我们在做的时候选择小的一边做就可以了。

这样就相当于启发式合并，时间复杂度 O(n\log n)

#include<bits/stdc++.h>
typedef long long LL;

using namespace std;
const int MAXN=2e6+10,P=998244353;
int n;
int l[MAXN],r[MAXN];
LL pw[MAXN],inv[MAXN],ctl[MAXN];
LL C(LL x,LL y) {
    if(x<y) return 0;
    return pw[x]*inv[y]%P*inv[x-y]%P;
}
int sz[MAXN];
LL ans;
void dfs(int u) {
    sz[u]=1;
    if(l[u]) dfs(l[u]);
    if(r[u]) dfs(r[u]);
    sz[u]+=sz[l[u]]+sz[r[u]];
}
void dfs1(int u,LL xs) {
    if(sz[l[u]]<=sz[r[u]]+1) {
        for(int i=0;i<sz[l[u]];++i) {
            (ans+=xs*ctl[i]%P*ctl[sz[u]-1-i]%P)%=P;
        }
    }
    else {
        ans=(ans+ctl[sz[u]]*xs%P)%P;
        for(int i=0;i<=sz[r[u]];++i) {
            ans=(ans-xs*ctl[i]%P*ctl[sz[u]-1-i]%P+P)%P;
        }
    }
    if(l[u]) dfs1(l[u],xs*ctl[sz[r[u]]]%P);
    if(r[u]) dfs1(r[u],xs);
}
int main () {
    scanf("%d",&n);
    for(int i=1;i<=n;++i) {
        scanf("%d%d",&l[i],&r[i]);
    }
    pw[0]=inv[0]=inv[1]=1;
    for(int i=1;i<=(n<<1);++i) {
        pw[i]=pw[i-1]*i%P;
    }
    for(int i=2;i<=(n<<1);++i) {
        inv[i]=(P-(P/i))*inv[P%i]%P;
    }
    for(int i=2;i<=(n<<1);++i) inv[i]=inv[i-1]*inv[i]%P;
    ctl[0]=1;
    for(int i=1;i<=n;++i) {
        ctl[i]=(C(i*2,i)-C(i*2,i-1)+P)%P;
    }
    for(int i=1;i<n;++i) {
        ans+=ctl[i];
    } ans%=P;
    dfs(1);
    dfs1(1,1);
    printf("%lld\n",ans);
    return 0;
}

P3978 [TJOI2015] 概率论

记 f_n 为大小为 n 的二叉树总数量， g_n 为 n 的二叉树的叶子总数量。

那么有结论 g_n=nf_{n-1} ，怎么来的结论。~~打表呀~~

然后答案就是 \frac {g_n}{f_n}=\frac {nf_{n-1}}{f_n}=\frac {n(n+1)}{2(2n-1)} 。

具体如何证明。

对于大小为 n-1 的二叉树你可以有 n 个位置去挂一个他的新的叶子结点，那么对于每个二叉树都有 n 个位置可以挂。

然后同时可以保证一定不会重复，所有就是 nf_{n-1}

然后就证明完了。

#include<bits/stdc++.h>
typedef long long LL;

using namespace std;
const int MAXN=110;
double n;
double f[MAXN],ctl[MAXN];
int main () {
    scanf("%lf",&n);
    printf("%.12lf",(double)n*(n+1)/(2*(2*n-1)));
//  ctl[0]=ctl[1]=1;
//  for(int i=2;i<=n;++i) {
//      ctl[i]=ctl[i-1]*(4*i-2)/(i+1);
//  }
//  f[1]=1;
//  for(int i=2;i<=n;++i) {
//      for(int j=0;j<i;++j) {
//          f[i]=f[i]+(2*f[j]*ctl[i-1-j]*ctl[j]);
//      }
//      f[i]=f[i]*1.0/ctl[i];
//  }
//  printf("%.9lf",f[n]);
    return 0;
}

P5014 水の三角(修改版)

容易发现，实际上可以枚举向右走的数量，然后转化成一个卡特兰数和插板法就好了，比较显然。

#include<bits/stdc++.h>
typedef long long LL;

using namespace std;
const int MAXN=2e6+10,P=998244353;
LL ksm(LL x,LL y) {
    LL ret=1;
    while(y) {
        if(y&1) ret=ret*x%P;
        x=x*x%P;
        y>>=1;
    }
    return ret;
}
LL n;
LL pw[MAXN],inv[MAXN];
LL C(LL x,LL y) {
    if(x<y) return 0;
    return pw[x]*inv[x-y]%P*inv[y]%P;
}
LL ctl(LL n,LL m) {
    return (C(n+m,n)-C(n+m,n+1)+P);
}
void vmain() {
    scanf("%lld",&n);
    LL a=sqrt(n)-1,k;
    while(n-(LL)a*(a-1)/2>a) ++a;
    k=n-(LL)a*(a-1)/2;
    LL ans=0;
    for(int i=0;i<k;++i) {
        LL _a=a-1-i,_k=k-1-i;
        ans+=C(_a+_k+i,i)*ctl(_a,_k)%P;
        if(ans>=P) ans-=P;
    }
    printf("%lld\n",ans);
}
int main () {
    pw[0]=inv[0]=1;
    for(int i=1;i<=2e6;++i) {
        pw[i]=pw[i-1]*i%P;
        inv[i]=ksm(pw[i],P-2);
    }
    int T;
    scanf("%d",&T);
    while(T--) vmain();
    return 0;
}

咕掉了，不会做的题P4769 [NOI2018] 冒泡排序

总结：

这个东西其实就是你得证明你求的东西是 catlan 数，然后再带入卡特兰的式子去优化他。

《卡特兰数》 学习总结

定义