Catalan数
Catalan数的计算公式是：c(2n,n)/n+1
它有3个公式，分别是Cn=c(2n,n)/n+1、Cn=C0Cn-1+C1Cn-2+......+Cn-1C0、Cn=Cn-1(4n+2)/(n+1)
Catalan数的应用十分广泛，有棋盘问题、括号问题、出栈序列问题等
下面给出两道求解Catalan数的例题：
由于数据非常大，所以需要用到高精度
在这道题中，使用的是Catalan数的第一个公式的变式
代码：
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 1e4+39+7;
struct node{
int a[N],len;
};
node init(){
node ret;
ret.len=1;ret.a[1]=1;
return ret;
}
node mul(node a,int k){
node ans;
for(int i=1;i<=a.len;i++)ans.a[i]=a.a[i]*k;
for(int i=2;i<=a.len;i++){
ans.a[i]+=ans.a[i-1]/10;
ans.a[i-1]%=10;
}
ans.len=a.len;
while(ans.a[ans.len]>10){
ans.a[ans.len+1]=ans.a[ans.len]/10;
ans.a[ans.len++]%=10;
}
return ans;
}
node chu(node a,int k){
node ans;
int t=0;
for(int i=a.len;i>=1;i--){
t=t*10+a.a[i];
ans.a[i]=t/k;
t%=k;
}
ans.len=a.len;
while(ans.a[ans.len]==0)ans.len--;
return ans;
}
node ans;int n;
int main(){
ans=init();
cin>>n;
for(int i=n+2;i<=n*2;i++)ans=mul(ans,i);
for(int i=1;i<=n;i++)ans=chu(ans,i);
for(int i=ans.len;i>=1;i--)cout<<ans.a[i];
return 0;
}
这道题可以直接递推Catalan数的第3个公式递推求解
代码：
#include<bits/stdc++.h>
#define ll long long
using namespace std;
int main(){
int n;ll ans=1;
cin>>n;
for(int i=1;i<=n;i++)ans=ans*(4*i-2)/(i+1);
cout<<ans;
return 0;
}
Stirling数
Stirling数分为第1类Stirling数和第2类Stiling数
第1类Stiling数的计算公式是s(n,k)=s(n-1,k-1)+(n-1)*s(n-1,k)，s(0,0)=1，s(k,0)=0
它的应用是将n个不同的元素分配到k个圆排列里，圆不能为空，求解方案数
第2类Stiling数的计算公式是S(n,k)=kS(n-1,k)+S(n-1,k-1)，S(0,0)=1，S(i,0)=0
它的应用是将n个不同的球分配到k个相同的盒子里，不能有空盒子，求解方案数
下面给出一道求解第2类Stiling数的例题
数据非常大，所以也需要高精度
直接使用计算公式求解即可
代码：
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 4e2+39+7,M = 1e2+39+7;
struct node{
int a[N],len;
};
node init(){
node ret;
ret.len=1;ret.a[1]=1;
return ret;
}
node mul(node a,int k){
node ans;
memset(ans.a,0,sizeof(ans.a));
ans.len=a.len;
for(int i=1;i<=ans.len;i++){
ans.a[i]+=a.a[i]*k;
if(ans.a[i]>=10){
ans.a[i+1]+=ans.a[i]/10;
ans.a[i]%=10;
if(i==ans.len)ans.len++;
}
}
return ans;
}
node add(node a,node b){
node ans;
memset(ans.a,0,sizeof(ans.a));
ans.len=max(a.len,b.len);
for(int i=1;i<=ans.len;i++){
ans.a[i]+=a.a[i]+b.a[i];
if(ans.a[i]>=10){
ans.a[i+1]+=ans.a[i]/10;
ans.a[i]%=10;
if(i==ans.len)ans.len++;
}
}
return ans;
}
node f[101][101];
int main(){
for(int i=1;i<=100;i++){
f[i][0].len=f[i][i].len=f[i][1].len=1;
f[i][0].a[1]=0;
f[i][i].a[1]=f[i][1].a[1]=1;
}
for(int i=2;i<=100;i++){
for(int j=2;j<i;j++){
f[i][j]=add(f[i-1][j-1],mul(f[i-1][j],j));
}
}
int n,m;
while(cin>>n>>m){
if(m>n){
cout<<0<<'\n';
continue;
}
for(int i=f[n][m].len;i>=1;i--)cout<<f[n][m].a[i];
cout<<'\n';
}
return 0;
}