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; }
标签:node,10,int,Stirling,len,Catalan,ret,ans From: https://www.cnblogs.com/zhanghx-blogs/p/17552312.html