卡特兰数 hdu 5673

本文主要是介绍卡特兰数 hdu 5673，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

卡特兰数的性质

卡特兰数有一些优美的性质，如

通项公式一     Cn=1n+1Cn2n=Cn2n−Cn−12n Cn=1n+1C2nn=C2nn−C2nn−1；

通项公式二     Cn=1n+1∑i=0n(Cin)2 Cn=1n+1∑i=0n(Cni)2；

递推公式一     Cn+1=2(2n+1)n+2Cn Cn+1=2(2n+1)n+2Cn，且 C0=1 C0=1；

递推公式二     Cn+1=∑i=0nCiCn−i Cn+1=∑i=0nCiCn−i，且 C0=1 C0=1；

增长速度     ΔCn∼4nn32π√ ΔCn∼4nn32π．

#include<cstdio>
#include<cstring>
#define MOD 1000000007
using namespace std;
long long inv[1000010],c[1000010],d[1000010];
void init()
{inv[1]=1;for(int i=2;i<1000010;i++)inv[i]=(MOD-MOD/i)*inv[MOD%i]%MOD ;d[0]=d[1]=1;for(int i=2;i<500010;i++)d[i]=d[i-1]*(4*i-2)%MOD *inv[i+1]%MOD; 
}
int main()
{init();int T,n;scanf("%d",&T);while(T--){long long res=0;scanf("%d",&n);c[0]=1;for(int i=1;i<=n;i++)c[i]=c[i-1]*(n-i+1)%MOD * inv[i] %MOD;for(int i=0;i<=n/2;i++)res=(res+d[i]*c[2*i])%MOD;printf("%lld\n",res);}
}

这篇关于卡特兰数 hdu 5673的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---