vijosP1388 二叉树数

vijosP1388 二叉树数

链接：https://vijos.org/p/1388

【思路】

Catalan数。根据公式h=C(2n,n)/(n+1)计算。首先化简为 (n+i)/i的积(1<=i<=n)

法一：

高精单精乘除。

法二：

唯一分解定理。将乘除操作转化为对质因子指数的加减，最后用高精单精乘起来。类于vijosP1137 组合数一题

【代码1】439ms

 #include<iostream>

 #include<cstring>

 using namespace std;

 struct Bign {

     int len;

     long long N[];

     Bign() {

         memset(N,,sizeof(N));

     }

 };

 int n;

 void multi(Bign& a,int x)

 {

     for(int j=;j<a.len;j++) a.N[j] *= x;

     int i=;

     while(i<a.len || a.N[i]>) {

         a.N[i+] += a.N[i]/;

         a.N[i] %= ;

         i++;                    //i++

     }

     if(a.N[i]) a.len=i+;  //判断

     else a.len=i;

 }

 void div(Bign& a,int x) {

     for(int i=a.len-;i>;i--) {  //由高位到低位

         a.N[i-] += a.N[i]%x*;

         a.N[i] /= x;

     }

     a.N[]/=x;  //最后一位

     while(a.N[a.len-]==) a.len--;  //删除前导0

 }

 int main() {

     cin>>n;

     Bign ans;

     ans.len=; ans.N[]=;

     for(int i=;i<=n;i++) {

         multi(ans,n+i);

         div(ans,i);

     }

     div(ans,n+);

     for(int i=ans.len-;i>=;i--) cout<<ans.N[i];

     return ;

 }

【代码2】52ms

 #include<iostream>

 #include<cstring>

 #include<vector>

 #include<cmath>

 using namespace std;

 const int maxn = +;

 struct Bign{

     int len,N[maxn];

     Bign() {

         memset(N,,sizeof(N));

     }

 };

 int e[maxn];

 int n,m,ans;

 vector<int> primes;

 void get_primes(int n) {

     bool su[maxn]; memset(su,true,sizeof(su));

     for(int i=;i<=n;i++) if(su[i]) {

         primes.push_back(i);

         if(i<=sqrt(n)) for(int j=i*i;j<=n;j+=i) su[j]=false;

         //i<=sqrt(n) 否则RE

     }

 }

 void calc(int x,int d) {

     for(int i=;i<primes.size();i++) {

         while(x%primes[i]==) {

             e[i] += d;

             x /= primes[i];

         }

         if(x==) break;

     }

 }

 void multi(Bign& a,int x)

 {

     for(int j=;j<a.len;j++) a.N[j] *= x;

     int i=;

     while(i<a.len || a.N[i]>) {

         a.N[i+] += a.N[i]/;

         a.N[i] %= ;

         i++;                    //i++

     }

     if(a.N[i]) a.len=i+;  //判断

     else a.len=i;

 }

 int main() {

     cin>>n;

     get_primes(*n+);

     for(int i=;i<=n;i++) {

         calc(n+i,);

         calc(i,-);

     }

     calc(n+,-);

     Bign ans; ans.len=; ans.N[]=;

     for(int i=;i<primes.size();i++){

         while(e[i]--) multi(ans,primes[i]);

     }

     for(int i=ans.len-;i>=;i--) cout<<ans.N[i];

     return ;

 }