bzoj1211: [HNOI2004]树的计数（purfer编码）

　　BZOJ1005的弱化版，不想写高精度就可以写这题嘿嘿嘿

　　purfer编码如何生成？每次将字典序最小的叶子节点删去并将其相连的点加入序列中，直到树上剩下两个节点，所以一棵有n个节点的树purfer编码长度为n-2。

　　purfer编码如何还原一棵树？从前往后扫purfer编码，每次找到不在编码中的没有被选择过的字典序最小的点，并将purfer编码第一个点与这个点连边并删去。

　　purfer编码的性质？

　　①度数为d[i]的点在purfer编码中出现d[i]-1次。

　　②每一个purfer编码对应一棵唯一的树。

　　知道了这些之后，我们就能大概有一个思路了，求多少棵树相当于求多少个purfer编码满足条件。

　　第i个点度数为d[i]，那么在purfer编码中出现d[i]-1次，编码的长度为n-2，于是总的方案数为：

bzoj1211: [HNOI2004]树的计数（purfer编码）

　　虽然答案不会爆long long但是计算过程会爆，于是必须分解质因数来写。

#include<iostream>

#include<cstring>

#include<cstdlib>

#include<cstdio>

#include<algorithm>

#define ll long long

using namespace std;

const int maxn=,inf=1e9;

int n,sum;

int cnt[maxn],d[maxn];

ll ans=;

void read(int &k)

{

    int f=;k=;char c=getchar();

    while(c<''||c>'')c=='-'&&(f=-),c=getchar();

    while(c<=''&&c>='')k=k*+c-'',c=getchar();

    k*=f;

}

void dec(int x,int y)

{

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

    while(x%i==)cnt[i]+=y,x/=i;

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

}

ll power(ll a,int b)

{

    ll ans=;

    while(b)

    {

        if(b&)ans*=a;

        a*=a;

        b>>=;

    }

    return ans;

}

int main()

{

    read(n);

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

    {

        read(d[i]);sum+=d[i]-;

        if(!d[i]&&n!=)return puts(""),;

    }

    if(sum!=n-)return puts(""),;

    for(int j=;j<=n-;j++)dec(j,);

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

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

    dec(j,-);

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

    if(cnt[i])ans*=power(i,cnt[i]);

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

    return ;

}

秒客网

bzoj1211: [HNOI2004]树的计数（purfer编码）

相关文章