首页 > 其他分享 >Catalan数和Stirling数

Catalan数和Stirling数

时间:2023-07-13 22:14:01浏览次数:55  
标签:node 10 int Stirling len Catalan ret ans

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数的例题:

P2532 [AHOI2012] 树屋阶梯

由于数据非常大,所以需要用到高精度

在这道题中,使用的是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;
}

 

  

P1044 [NOIP2003 普及组] 栈

这道题可以直接递推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数的例题

P1655 小朋友的球

数据非常大,所以也需要高精度

直接使用计算公式求解即可

代码:

#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

相关文章

  • Wallis 公式、Stirling 公式与正态分布
    参考:张筑生《数学分析新讲》第二册[1]张颢《概率论》[2]Wikipedia,MathStackExchange,etc.1WarmupExample1求limn→∞(2n−1)!!(2n)!!=limn→∞1×3×5×⋯×(2n−1)2×4×6×⋯×2nSolution.用放缩2k>(2k−1)(2k+1)拆分母即得(2n−1)!!(2n)!!<12n+1∼0......
  • 卡特兰数(Catalan number)
    Catalan数列目录目录Catalan数列目录定义Number说明表示1.递推定义2.递推关系3.通项公式4.通项公式II证明1.公式42.公式13.公式34.公式2证毕推荐链接定义Numbe......
  • 【XSY4320】Catalan(组合意义,DP,多项式)
    题面:Catalan题解:假瑞的做法orz考虑用组合意义来做,观察递推式\(f_i=\frac{1}{i}\sum_{j=0}^{i-1}f_jf_{i-j-1}\),它除了和卡特兰数递推式很像之外,还和二叉树计数的递推......
  • 【POJ1430】Binary Stirling Numbers(第二类斯特林数,组合数)
    求\(\begin{Bmatrix}n\\m\end{Bmatrix}\bmod2\)的值。由第二类斯特林数的递推公式:\[\begin{Bmatrix}n\\m\end{Bmatrix}=\begin{Bmatrix}n-1\\m-1\end{Bmatrix}+m\begi......