洛谷 P2290 [HNOI2004]树的计数

题目描述

输入输出格式

输入格式：

输入文件第一行是一个正整数n，表示树有n个结点。第二行有n个数，第i个数表示di，即树的第i个结点的度数。其中1<=n<=150，输入数据保证满足条件的树不超过10^17个。

输出格式：

输出满足条件的树有多少棵。

输入输出样例

输入样例#1：

4

2 1 2 1

输出样例#1：2

题解：质因数分解+prufer数列
以前学过prufer数列...全忘了....
n个点的无根树对应的数列的长度为N-2,这说明一个n个点的无根树有n^(n-2)种
树转prufer数列：将编号最小的叶子结点删掉，将与叶子结点相邻的点加入prufer数列
prufer数列转树：对于集合G={1,2,3，..n}每次找出不在当前prufer数列里有的最小的元素x
与prufer数列的首项连边，删除首项与x，直到剩下两个元素连边...
结点i的度为x，那么i出现的次数为x-1
对于i号点度数为d[i]的 无根树 树的种数有 (n - 2) ! / ( (d1 - 1)! (d2 - 1)! ……(dn - 1)! 
参考
会爆long long 分解质因数

代码：

#include<iostream>

#include<cstdio>

#define over printf("0\n")

#define end return 0

using namespace std;

int n,x,ok,cnt[];

long long ans=;

void chai(int x,int y){

    for(int i=;i*i<=x;i++){

        while(x%i==){

            cnt[i]+=y;

            x/=i;

        }

    }

    if(x>)cnt[x]+=y;

}

int main(){

    scanf("%d",&n);

    for(int i=;i<=n-;i++)chai(i,);

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

        scanf("%d",&x);ok+=x-;

        if(!x&&n!=){

            over; end;

        }

        for(int j=;j<=x-;j++)chai(j,-);

    }

    if(ok!=n-){

        over;end;

    }

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

     for(int j=;j<=cnt[i];j++)

      ans=ans*i;

    printf("%lld\n",ans);

    return ;

}