点击刷新
卡特兰数是一种经典的组合数，前几项为：
1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796,58786, 208012, 742900, 2674440, 9694845, 35357670, 129644790, 477638700, 1767263190, 6564120420, 24466267020, 91482563640, 343059613650, 1289904147324, 4861946401452, ...
计算公式为：h(n)=C(2n,n)/(n+1)
令h(0)=1,h(1)=1;
卡特兰数的递推式：h(n)= h(0)*h(n-1) + h(1)*h(n-2) + ... + h(n-1)h(0) (n>=2)。
//35以内的卡特兰数 void init() { long long h[36]; h[0] = h[1] = 1; for (int i = 2; i < 36; i++) { h[i] = 0; for (int j = 0; j < i; j++) h[i] = h[i] + h[j] * h[i - j - 1]; } }
大于35时，求h(n)%p，用卢卡斯定理
h(n) % p = (Lucas(2n, n, p) - Lucas(2n, n - 1, p) + p) % p
ll exp_mod(ll a, ll b, ll p) { ll res = 1; while (b) { if (b & 1) res = (res * a) % p; a = (a * a) % p; b >>= 1; } return res; } ll comb(ll a, ll b, ll c) { if (a < b) return 0; if (a == b) return 1; if (b > a - b) b = a - b; ll ans = 1, ca = 1, cb = 1; for (ll i = 0; i < b; i++) { ca = (ca * (a - i)) % p; cb = (cb * (b - i)) % p; } ans = (ca * exp_mod(cb, p - 2, p)) % p; return ans; } ll lucas(ll n, ll m, ll p) { //Lucas求C(n,m) ll ans = 1; while (n && m && ans) { ans = (ans * comb(n % p, m % p, p)) % p; n /= p; m /= p; } return ans; }
求卡特兰大数
int a[101][101], b[101]; //b[i]保存的是第i位卡特兰数的长度 //a[i]数组保存的是第i位卡特兰数的数值，高位存高位，低位存低位 void catalan() { int len, carry, temp; a[1][0] = b[1] = 1; len = 1; for (int i = 2; i <= 100; i++) { for (int j = 0; j < len; j++) a[i][j] = a[i - 1][j] * (4 * (i - 1) + 2); carry = 0; for (int j = 0; j < len; j++) { temp = a[i][j] + carry; a[i][j] = temp % 10; carry = temp / 10; } while (carry) { a[i][len++] = carry % 10; carry /= 10; } carry = 0; for (int j = len - 1; j >= 0; j--) { temp = carry * 10 + a[i][j]; a[i][j] = temp / (i + 1); carry = temp % (i + 1); } while (!a[i][len - 1]) len--; b[i] = len; } }
#include <iostream> using namespace std; int a[105][100]; int main( ) { int n,len; memset(a,0,sizeof(a)); a[1][1]=1; a[1][0]=1; //a[n][0] 保存长度 a[2][1]=2; a[2][0]=1; len=1; for(int i=3; i<=100; i++) { int yu(0),t; for(int j=1; j<=len; j++) { //乘的模拟 t=(a[i-1][j])*(4*i-2)+yu; a[i][j]=t%10; yu=t/10; } while(yu) { a[i][++len]=yu%10; yu/=10; } for(int j=len; j>=1; j--) { //除的模拟 t=a[i][j]+yu*10; a[i][j]=t/(i+1); yu=t%(i+1); } while(!a[i][len]) len--; a[i][0]=len; } while(cin>>n) { for(int i=a[n][0]; i>0; i--) cout<<a[n][i]; cout<<endl; } return 0; }
© 著作权归作者所有
举报
发表评论
0/200
