一个有n个结点的树，设它的结点分别为v1, v2, …, vn，已知第i个结点vi的度数为di，
问满足这样的条件的不同的树有多少棵。给定n，d1, d2, …, dn，
编程需要输出满足d(vi)=di的树的个数。
Input
第一行是一个正整数n，表示树有n个结点。
第二行有n个数，第i个数表示di，即树的第i个结点的度数。
其中1<=n<=150，输入数据保证满足条件的树不超过10^17个。
Output
输出满足条件的树有多少棵。
Sample Input
4
2 1 2 1
Sample Output
2
sol:本题利用Purfer序的一个性质，若树中一个结点的度为i，则它在Purfer序中出现的次数是i-1。
如上图，7个结点,1~7结点的度依次为2，3，1，3，1，1，1。各个点的度-1后依次为1，2，0，2，0，0，0。
purfer序为(2,2,1,4,4)，即1号结点出现1次，2号结点出现2次，4号结点出现2次。
本题给出了结点个数及每个结点的度，我们就知道它在purfer序中出现的次数，从而算出满足条件的树。
如上图满足条件的树为c(5,1)*c(4,2)*c(2,2),即在purfer序的5个位置中，任选1个位置放1号结点，然后从剩下的4个位置中放2号结点，最后剩下2个位置放4号结点。
注意：实际求组合数的过程要分解质因数，不然爆long long。
1 #include<iostream> 2 #include<cstdio> 3 #include<cmath> 4 #include<cstring> 5 #define ll long long 6 using namespace std; 7 inline int read() 8 { 9 int x=0,f=1;char ch=getchar(); 10 while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} 11 while(ch>='0'&&ch<='9'){x*=10;x+=ch-'0';ch=getchar();} 12 return x*f; 13 } 14 int n,m,tot,cnt; 15 int d[155],num[155],pri[155]; 16 ll s[25],ans=1; 17 bool jud(int x) 18 { 19 for(int i=2;i<=sqrt(x);i++) 20 if(x%i==0)return 0; 21 return 1; 22 } 23 void getpri() 24 { 25 for(int i=2;i<=150;i++) 26 if(jud(i))pri[++cnt]=i; 27 } 28 void solve(ll x,int f) 29 { 30 for(int i=1;i<=cnt;i++) 31 { 32 if(x<=1)return; 33 while(x%pri[i]==0) 34 {num[i]+=f;x/=pri[i];}//怎么是num[i]+=f； 35 } 36 } 37 int main() 38 { 39 s[1]=1; 40 for(int i=2;i<=22;i++) 41 s[i]=s[i-1]*i; 42 getpri(); 43 n=read(); 44 if(n==1) 45 { 46 int x=read(); 47 if(!x)printf("1"); 48 else printf("0"); 49 return 0; 50 } 51 for(int i=1;i<=n;i++) 52 { 53 d[i]=read(); 54 if(!d[i]){printf("0");return 0;} 55 d[i]--; 56 tot+=d[i]; 57 } 58 if(tot!=n-2){printf("0");return 0;} 59 solve(s[n-2],1); 60 for(int i=1;i<=n;i++) 61 solve(s[d[i]],-1); 62 for(int i=1;i<=cnt;i++) 63 while(num[i]--) 64 ans*=pri[i]; 65 printf("%lld",ans); 66 return 0; 67 }