问n个不同的节点可以组成多少种不同的树
首先考虑对于相同的n个节点可以形成多少种树,设DP[N]为N个节点的情况,我们分别考虑左右子树的情况,假设左子树有i个节点,那么相对的右子树就存在N-i-1个节点,
那么就有DP[N]=DP[i]*DP[N-i-1] i=0.1.2....N-1
这是节点都相同的情况,那么,对于任意一个由k个节点组成的其中一种树,当这k个节点都不相同时,考虑k的全排列个数就是这种树的所有可能情况,k的全排列个数就是k!
因此最后对每个i
DP[i]*=i!,就是最后的答案
参考了SJTU的大数模板
#include<iostream> #include<cstring> #define lld long long int const int MAXN=9999; const int DLEN=4; using namespace std; class BigNum{ private: int a[1800]; int len; public: BigNum(){len=1;memset(a,0,sizeof(a));} BigNum(const char*); BigNum(const int); BigNum(const BigNum&); BigNum& operator=(const BigNum&); BigNum operator+(const BigNum&)const; BigNum operator-(const BigNum&)const; BigNum operator*(const BigNum&)const; BigNum operator/(const int&)const; BigNum operator^(const int&)const; int operator%(const int &)const; bool operator>(const BigNum&)const; void print(); }; BigNum::BigNum(const int n){ int c,d=n; len=0; memset(a,0,sizeof(a)); while(d>MAXN){ c=d-(d/(MAXN+1))*(MAXN+1); d=d/(MAXN+1); a[len++]=c; } a[len++]=d; } BigNum::BigNum(const char *s){ int t,k,index,l,i; memset(a,0,sizeof(a)); l=strlen(s); len=l/DLEN; if(l%DLEN) len++; index=0; for(i=l-1;i>=0;i-=DLEN){ t=0; k=i-DLEN+1; if(k<0) k=0; for(int j=k;j<=i;j++) t=t*10+s[j]-'0'; a[index++]=t; } } BigNum::BigNum(const BigNum &T):len(T.len){ int i; memset(a,0,sizeof(a)); for(i=0;i<len;i++) a[i]=T.a[i]; } BigNum& BigNum::operator=(const BigNum& n){ len=n.len; memset(a,0,sizeof(a)); int i; for(i=0;i<len;i++) a[i]=n.a[i]; return *this; } BigNum BigNum::operator+(const BigNum &T)const{ BigNum t(*this); int i,big; big=T.len>len?T.len:len; for(i=0;i<big;i++){ t.a[i]+=T.a[i]; if(t.a[i]>MAXN){ t.a[i+1]++; t.a[i]-=MAXN+1; } } if(t.a[big]!=0) t.len=big+1; else t.len=big; return t; } BigNum BigNum::operator-(const BigNum &T)const{ int i,j,big; bool flag; BigNum t1,t2; if(*this>T){ t1=*this; t2=T; flag=0; } else{ t1=T; t2=*this; flag=1; } big=t1.len; for(i=0;i<big;i++){ if(t1.a[i]<t2.a[i]){ j=i+1; while(t1.a[j]==0) j++; t1.a[j--]--; while(j>i) t1.a[j--]+=MAXN; t1.a[i]+=MAXN+1-t2.a[i]; } else t1.a[i]-=t2.a[i]; } t1.len=big; while(t1.a[len-1]==0&&t1.len>1){ t1.len--; big--; } if(flag) t1.a[big-1]=0-t1.a[big-1]; return t1; } BigNum BigNum::operator*(const BigNum & T) const { BigNum ret; int i,j,up; int temp,temp1; for(i = 0 ; i < len ; i++) { up = 0; for(j = 0 ; j < T.len ; j++) { temp = a[i] * T.a[j] + ret.a[i + j] + up; if(temp > MAXN) { temp1 = temp - temp / (MAXN + 1) * (MAXN + 1); up = temp / (MAXN + 1); ret.a[i + j] = temp1; } else { up = 0; ret.a[i + j] = temp; } } if(up != 0) ret.a[i + j] = up; } ret.len = i + j; while(ret.a[ret.len - 1] == 0 && ret.len > 1) ret.len--; return ret; } BigNum BigNum::operator/(const int & b) const {BigNum ret; int i,down = 0; for(i = len - 1 ; i >= 0 ; i--) { ret.a[i] = (a[i] + down * (MAXN + 1)) / b; down = a[i] + down * (MAXN + 1) - ret.a[i] * b; } ret.len = len; while(ret.a[ret.len - 1] == 0 && ret.len > 1) ret.len--; return ret; } int BigNum::operator %(const int & b) const { int i,d=0; for (i = len-1; i>=0; i--) { d = ((d * (MAXN+1))% b + a[i])% b; } return d; } BigNum BigNum::operator^(const int & n) const { BigNum t,ret(1); if(n<0)exit(-1); if(n==0) return 1; if(n==1) return *this; int m=n; while(m>1) { t=*this; int i; for(i=1;i<<1<=m;i<<=1) { t=t*t; } m-=i; ret=ret*t; if(m==1) ret=ret*(*this); } return ret; } bool BigNum::operator>(const BigNum & T) const {int ln; if(len > T.len) return true; else if(len == T.len) { ln = len - 1; while(a[ln] == T.a[ln] && ln >= 0) ln--; if(ln >= 0 && a[ln] > T.a[ln]) return true; else return false; } else return false; } void BigNum::print() { int i; cout << a[len - 1]; for(i = len - 2 ; i >= 0 ; i--) { cout.width(DLEN); cout.fill('0'); cout << a[i]; } } BigNum DP[101]; BigNum tmp[101]; int main(){ for(int i=0;i<=100;i++){ if(i==0) tmp[i]=1; else tmp[i]=tmp[i-1]*i; } for(int i=0;i<=100;i++){ if(i==0||i==1) DP[i]=1; else{ DP[i]=0; for(int j=0;j<=i-1;j++){ DP[i]=DP[i]+DP[j]*DP[i-1-j]; } } } for(int i=0;i<=100;i++) DP[i]=DP[i]*tmp[i]; int n; while(cin>>n&&n){ DP[n].print(); cout<<endl; } return 0; }