定义
我也不知道
我们假设卡特兰数\(C(n)\)的定义是从\((0,0\))出发，沿着轴前进到达\((n,n)\)只能向右或向上且任意时刻都满足此时所在的位置\((x,y)\)满足\(y\ge x\)的方案数。
如下图就是一条符合条件的路径(\(HI\)也是这条路径上的)
要计算这个东西的方案数自然不太容易，但考虑正难则反。总共的方案数是\(\tbinom{2n}{n}\) ，接下来只需要求不符合条件的方案数就行了。
经过我们的人类智慧，不满足条件的方案一定会经过\(y=x-1\)这条直线，于是我们在路径与这条直线首次接触的部分标个记号，这个记号前面的保持不变，后面的则沿着\(y=x-1\)对称出去，则对称后的路径绝对是在\((n-1,n+1)\)结束，是吧？
那要从\((0,0)\)走到\((n-2,n)\)且只能向右或向上，那方案数就是\(\tbinom{2n}{n-1}\)，是吧？
那符合原来的条件的方案数就是\(\tbinom{2n}{n}-\tbinom{2n}{n-1}\)
\(原式=\frac{(2n)!}{n!n!}-\frac{(2n)!}{(n-1)!(n+1)!}\)
\(=\frac{1}{n+1}(\frac{(2n)!\times (n+1)}{n!n!}-\frac{(2n)!}{(n-1)!n!})\)
\(=\frac{1}{n+1}(\frac{(2n)!\times (n+1)}{n!n!}-\frac{n\times(2n)!}{n!n!})\)
\(=\frac{1}{n+1}(\frac{(2n)!}{n!n!})\)
\(=\frac{\tbinom{2n}{n}}{n+1}\)
所以我是不是只需要证明\(\tbinom{2n}{n}=\frac{\tbinom{2n}{n-1}}{n}\times(n+1)\)就行了？
\(\frac{\tbinom{2n}{n-1}}{n}\times(n+1)=\frac{(2n)!}{(n-1)!(n+1)!\times n\div (n+1)}\)
\(=\frac{(2n)!}{n!n!}\)
\(=\tbinom{2n}{n}\)
呵呵。
不对这好像已经不是定义了吧？
二阶递推式
直接给结论然后愉快跑路：
\(C(n)=\sum_{i=1}^{n} C(i-1)C(n-i)\)
但是由于作者常年不锻炼，跑不动，所以还得证明。
我们找到路径上除了起点第一个满足\(x=y\)的点，设这个点为\((x,x)\)，\(x\in [1,n]\)。
显然，在这种情况下，图里已经有\(4\)个确定的步骤：\((0,0)->(0,1)\)，\((x-1,x)->(x,x)\)，\((x,x)->(x,x+1)\)，\((n-1,n)->(n,n)\)，计算时需要排除。
从\((0,0)\)到\((x,x)\)，\(\color{red}{方案数是C(x-1)而非C(x)！！！要排除重复！！！}\)
从\((x,x)\)到\((n,n)\)，方案数是\(C(n-x)\)
乘法原理都学过吧？
一阶递推式
\(C(n+1)=\frac{4n+2}{n+2}C(n)\)你都看到这里了，所以这个公式想必是人都能自己证明，于是我走了。
但是由于作者常年不锻炼，走不动，所以还得证明。
\(C(n+1)=\frac{\tbinom{2n+2}{n+1}}{n+2}\)
\(=\frac{(2n+2)!}{(n+1)!(n+1)!(n+2)}\)
\(=\frac{(2n)!}{n!n!(n+1)}\times \frac{(2n+1)(2n+2)}{(n+1)(n+2)}\)
\(=C(n)\times \frac{4n+2}{(n+2)}\)
讲了这么多我还是觉得直接求更优秀，不过第二种不需要逆元
懒得写不会写扩展卡特兰数了，下次有机会再补上再去学。
代码
附上三种方法求\(1\sim n\)卡特兰数的代码，\(1\le n\le 2\times 10^3\)，对\(mod=998244353\)取模。
直接求
#include<bits/stdc++.h>
using namespace std;
#define mod 998244353
#define int long long
int n,m,i,j,f[4003],g[4003],p,ans;
int po(int x,int y){int s=1;while(y){if(y%2){s*=x;s%=mod;}x*=x;x%=mod;y/=2;}return s;
}
int c(int x,int y){if(y<0||x<y) return 0;return f[x]*g[y]%mod*g[x-y]%mod;
}
signed main()
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);cin>>n;f[0]=g[0]=1;for(i=1;i<=n*2;i++){f[i]=f[i-1]*i%mod;g[i]=po(f[i],mod-2);}for(i=1;i<=n;i++){p=c(2*i,i)-c(2*i,i-1);if(p<0) p+=mod;cout<<p<<" ";}return 0;
}
二阶递推
#include<bits/stdc++.h>
using namespace std;
#define mod 998244353
#define int long long
int n,m,i,j,p,ans,c[4003];
signed main()
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);cin>>n;c[0]=1;for(i=1;i<=n;i++){for(j=1;j<=n;j++){c[i]+=c[j-1]*c[i-j]%mod;c[i]%=mod;}cout<<c[i]<<" ";}return 0;
}
一阶递推
#include<bits/stdc++.h>
using namespace std;
#define mod 998244353
#define int long long
int n,m,i,j,p,ans,c[4003];
int po(int x,int y){int s=1;while(y){if(y%2){s*=x;s%=mod;}x*=x;x%=mod;y/=2;}return s;
}
signed main()
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);cin>>n;c[0]=1;for(i=1;i<=n;i++){c[i]=c[i-1]*(4*i-2)%mod*po(i+1,mod-2)%mod;cout<<c[i]<<" ";}return 0;
}