[bzoj1005][HNOI2008][明明的烦恼] (高精度+prufer定理)

Description

　　自从明明学了树的结构,就对奇怪的树产生了兴趣......给出标号为1到N的点,以及某些点最终的度数,允许在
任意两点间连线,可产生多少棵度数满足要求的树?

Input

　　第一行为N(0 < N < = 1000),
接下来N行,第i+1行给出第i个节点的度数Di,如果对度数不要求,则输入-1

Output

　　一个整数,表示不同的满足要求的树的个数,无解输出0

Sample Input

-

-

Sample Output

HINT

　　两棵树分别为1-2-3;1-3-2

Solution

填昨天的坑

根据prufer定理，用排列组合推出ans=(n-2)!/[(D1-1)!(D2-1)!···(Dk-1)!left!] * m^left

其中left=(n-2)-(D1-1)-(D2-1)-···-(Dk-1)

哦，还要注意特判，当无解时，高精度数组长度为0，直接输出0就行了

PoPoQQQ的代码很优雅

Code：

#include <stdio.h>

#include <memory.h>

#define ll long long

struct num {

    int top;

    ll x[];

    num(ll a=) {

        memset(x,,sizeof x );

        top=;

        x[]=a; }

    num operator*(const num b) {

        num tmp;

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

            for(int j=; j<=b.top; j++)

                tmp.x[i+j-]+=x[i]*b.x[j],

                tmp.x[i+j]+=tmp.x[i+j-]/,

                tmp.x[i+j-]%=;

        tmp.top=top+b.top;

        if(!tmp.x[tmp.top])

            tmp.top--;

        return tmp; } }ans();

void Q_pow(int x,int p) {

    num tmp(x);

    for(;p;p>>=,tmp=tmp*tmp)

        if(p&)

            ans=ans*tmp; }

int n,m,lef,cnt[];

void factorZ(int x,int d) {

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

        while(!(x%i))

            cnt[i]+=d,

            x/=i;

    if(x^)cnt[x]+=d; }

int main() {

    scanf("%d",&n);

    lef=n-;

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

        factorZ(i,);

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

        int x;

        scanf("%d",&x);

        if(~x) {

            if(x>) {

                lef-=x-;

                for(int i=;i<=x-;i++)

                    factorZ(i,-); } }

        else ++m; }

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

        factorZ(i,-);

    factorZ(m,lef);

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

        if(cnt[i])

            Q_pow(i,cnt[i]);

    printf("%lld",ans.x[ans.top]);

    for(int i=ans.top-;i;i--)

        printf("%08lld",ans.x[i]);

    return ; }