bzoj 1005: [HNOI2008]明明的烦恼(Prufer序列,组合数学,关于n!素数分解的一个定理)

题目链接

1005: [HNOI2008]明明的烦恼

Time Limit: 1 Sec Memory Limit: 162 MB
Submit: 4772 Solved: 1865
[Submit][Status][Discuss]

Description

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

Input

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

Output

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

Sample Input

3
1
-1
-1

Sample Output

HINT

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

Source

[Submit][Status][Discuss]

首先，说一说树的prufer序列：

Prufer序列

把一棵树进行以下操作：

1.找到编号最小的叶节点，删除这个节点，然后与这个叶节点相连的点计入序列

2.反复进行1，直到这棵树只剩下两个节点时，退出

比如说这个图(来自度受百科)

最小叶节点为2，删除2，将3计入序列

最小叶节点为4，删除4，将5计入序列

最小叶节点为5，删除5，将1计入序列

最小叶节点为1，删除1，将3计入序列

图中只剩下两个节点，退出

于是得到这棵树的Prufer序列为{3,5,1,3}

这样可以得到一个长度为n-2的序列。很容易证明，树和Prufer序列是一一对应的

Prufer序列显然满足一个性质：一个点若度数为d，则一定在Prufer序列中出现了d-1次

除此之外，还有一个重要的定理:

黄学长博客

一下是博客题解内容：

该题运用到了树的prufer编码的性质：

(1)树的prufer编码的实现

不断删除树中度数为1的最小序号的点，并输出与其相连的节点的序号直至树中只有两个节点

(2)通过观察我们可以发现

任意一棵n节点的树都可唯一的用长度为n-2的prufer编码表示

度数为m的节点的序号在prufer编码中出现的次数为m-1

(3)怎样将prufer编码还原为一棵树？？

从prufer编码的最前端开始扫描节点，设该节点序号为 u ,寻找不在prufer编码的最小序号且没有被标记的节点 v ，连接 u,v,并标记v，将u从prufer编码中删除。扫描下一节点。

该题需要将树转化为prufer编码：

n为树的节点数，d[ ]为各节点的度数，m为无限制度数的节点数。

则

所以要求在n-2大小的数组中插入tot各序号，共有

种插法；

在tot各序号排列中，插第一个节点的方法有

种插法；

插第二个节点的方法有

种插法；

………

另外还有m各节点无度数限制，所以它们可任意排列在剩余的n-2-tot的空间中，排列方法总数为

；

根据乘法原理：

然后就要高精度了…..但高精度除法太麻烦了，显而易见的排列组合一定是整数，所以可以进行质因数分解，再做一下相加减。

关于n!质因数分解有两种方法，第一种暴力分解，这里着重讲第二种。

若p为质数，则n!可分解为一个数*

，其中

且

<n（此处应为<=)

所以

——转自怡红公子

由于这题要大整数，我懒得写，于是写了个这一题的削弱版本：bzoj1211：链接

1211: [HNOI2004]树的计数

Time Limit: 10 Sec Memory Limit: 162 MB
Submit: 2347 Solved: 824
[Submit][Status][Discuss]

Description

一个有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

HINT

Source

[Submit][Status][Discuss]

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<vector>
#include<queue>
#include<stack>
using namespace std;
#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define pb push_back
#define fi first
#define se second
typedef vector<int> VI;
typedef long long ll;
typedef pair<int,int> PII;
const int inf=0x3fffffff;
const ll mod=1000000007;
const int maxn=200+10;
int prime[maxn],deg[maxn];
ll fp(int i,int y)
{
    ll ans=1,t=i;
    while(y)
    {
        if(y&1) ans=ans*t;
        t=t*t;
        y/=2;
    }
    return ans;
}
void getPrim()
{
    for(int i=2;i<maxn;i++)
    {
        if(!prime[i])
        {
            prime[++prime[0]] = i;
        }
        for(int j=1;(j<=prime[0])&&(i*prime[j]<maxn);j++)
        {
            prime[prime[j]*i] = 1;
            if(i%prime[j]==0) break;
        }
    }
}
int p1[maxn],p2[maxn];
int p[maxn];
void get(int x)
{
    for(int i=1;prime[i]<=x&&i<=prime[0];i++)
    {
        int t=prime[i];
        int cnt=0;
        while(t<=x) //
        {
            cnt+=x/t;
            t=t*prime[i];
        }
        p2[prime[i]]+=cnt;
    }
}
int main()
{
    int n,tot=0;
    getPrim();
    scanf("%d",&n);
    if(n==1)
    {
        int u;
        scanf("%d",&u);
        if(u!=0) puts("0");
        else puts("1");
        return 0;
    }
    rep(i,1,n+1)
    {
        scanf("%d",&deg[i]);
        if(deg[i]<=0)
        {
            puts("0");return 0;
        }
        tot+=deg[i]-1;
    }
    if(tot!=n-2){puts("0");return 0;}
    for(int i=1;prime[i]<=n-2&&i<=prime[0];i++)
    {
        int t=prime[i];
        int cnt=0;
        while(t<=n-2) //
        {
            cnt+=(n-2)/t;
            t=t*prime[i];
        }
        p1[prime[i]]+=cnt;
    }
    rep(i,1,n+1) get(deg[i]-1);
    ll ans=1;
    rep(i,1,prime[0]+1)
    {
        int cnt=p1[prime[i]]-p2[prime[i]];
        if(cnt)
        {
            ans*=fp(prime[i],cnt);
        }
    }
    printf("%lld
",ans);
    return 0;
}