【bzoj1005】[HNOI2008]明明的烦恼

2015.04.20 16:31 Mon | 5次阅读 | 旧日oi | 固定链接 | 源码

Description

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

Input

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

Output

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

Sample Input

3
1
-1
-1

Sample Output

2

HINT

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

题解

树的purfer编码,,shenmegui……
但是知道了之后就觉得好水了
purfer编码就是说,每次找度数为1且编号最小的点删掉,同时记录这个点的父亲,删到剩两个点为止形成的序列。每个树的purfer编码是唯一确定的。每个purfer编码也唯一对应一颗树,对应方式为:从头枚举purfer编码中的节点,设为u,选取度数最小的且没标记过的且不在编码序列中的点v和u连边,然后标记点v,删除点u……总之看这里吧
http://www.cnblogs.com/zhj5chengfeng/archive/2013/08/23/3278557.html
然后就是公式题了
对阶乘质因数分解的方法也很有意思,看hzwer的博客吧,证明也不难。

我的程序

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#define mod 1000000
#define ll long long
using namespace std;
int n,sum,tot;
int d[1005],ans[1005],prime[1005],cnt;
bool vis[1005];
void get_prime(int lim)
{
    for(int i=2;i<=lim;i++)
    {
        if(!vis[i]) prime[++cnt]=i;
        for(int j=1;j<=cnt&&prime[j]*i<=lim;j++)
        {
            vis[i*prime[j]]=1;
            if(i%prime[j]==0) break;
        }
    }
}
int final[1000000],len=1;
int main()
{
    cin>>n;
      if(n==1)
         {
                int x;cin>>x;
                if(!x)puts("1");
                else puts("0");
                return 0;
        }
    for(int i=1;i<=n;i++)
    {
        cin>>d[i];
        if(!d[i])
        {
            puts("0");
            return 0;
        }
        if(d[i]==-1)
        {
            tot++;
            continue;
        }
        sum+=d[i]-1;
    }
    if(sum>n-2)
    {
        puts("0");
        return 0;
    }
    d[n+1]=n-1-sum;
    final[1]=1;
    get_prime(n-2);
    for(int i=1;i<=cnt;i++)
    {
        int tmp=prime[i];
        while(tmp<=n-2)
        {
            ans[i]+=(n-2)/tmp;
            tmp*=prime[i];
        }
        for(int j=1;j<=n+1;j++)
        if(d[j]!=-1)
        {
            tmp=prime[i];
            while(tmp<=d[j]-1)
            {
                ans[i]-=(d[j]-1)/tmp;
                tmp*=prime[i];
            }
        }
        for(int j=1;j<=ans[i];j++) 
        {
            for(int k=1;k<=len;k++)
            final[k]*=prime[i];
            for(int k=1;k<=len;k++)
            final[k+1]+=final[k]/10,final[k]=final[k]%10;
            while(final[len+1]) len++,final[len+1]+=final[len]/10,final[len]%=10;
        }
    }
    for(int i=1;i<=n-2-sum;i++)
    {
        for(int k=1;k<=len;k++)
        final[k]*=tot;
        for(int k=1;k<=len;k++)
        final[k+1]+=final[k]/10,final[k]=final[k]%10;           
        while(final[len+1]) len++,final[len+1]+=final[len]/10,final[len]%=10;
    }
    for(int i=len;i;i--) printf("%d",final[i]);
    return 0;
}```