首页 > 代码库 > bzoj1005: [HNOI2008]明明的烦恼

bzoj1005: [HNOI2008]明明的烦恼

2024-09-04 07:37:39   215人阅读

1005: [HNOI2008]明明的烦恼

Time Limit: 1 Sec  Memory Limit: 162 MB

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

膜拜PoPoQQQ大爷，题解http://blog.csdn.net/popoqqq/article/details/40182169

树的Prufer编码，以下内容摘自度娘：

Prufer数列是无根树的一种数列。在组合数学中，Prufer数列由有一个对于顶点标过号的树转化来的数列，点数为n的树转化来的Prufer数列长度为n-2。它可以通过简单的迭代方法计算出来，一个树对应一个Prufer数列。

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

于是这就变成了一个排列组合的问题了

令每个已知度数的节点的度数为di，有n个节点，m个节点未知度数，left=(n-2)-(d1-1)-(d2-1)-...-(dk-1)

已知度数的节点可能的组合方式如下

(n-2)!/(d1-1)!/(d2-1)!/.../(dk-1)!/left!

剩余left个位置由未知度数的节点随意填补，方案数为m^left

于是最后有

ans=(n-2)!/(d1-1)!/(d2-1)!/.../(dk-1)!/left! * m^left

答案很显然有高精度，为了避免高精度除法我们可以对每个阶乘暴力分解质因数，对指数进行加减操作即可

/**************************************************************
    Problem: 1005
    User: zhouyuyang
    Language: C++
    Result: Accepted
    Time:40 ms
    Memory:1348 kb
****************************************************************/
 
#include<iostream>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cstring>
#include<queue>
#define ll long long
ll mo=1000000000;
using namespace std;
struct bignum{
    ll a[405];
    bignum operator * (const bignum b) const{
        bignum c;
        memset(c.a,0,sizeof(c.a));
        for (int i=1;i<=a[0];i++){
            ll x=0;
            for (int j=1;j<=b.a[0];j++){
                x+=a[i]*b.a[j]+c.a[i+j-1];
                c.a[i+j-1]=x%mo;
                x/=mo;
            }
            c.a[i+b.a[0]]=x;
        }
        c.a[0]=a[0]+b.a[0];
        while (!c.a[c.a[0]]&&c.a[0]) c.a[0]--;
        return c;
    }
}b,c,ans;
int a[1005],d[1005],n,m,s;
inline void chai(int x,int y){
    for (int i=2;i*i<=x;i++)
        while (x%i==0){
            x/=i;
            a[i]+=y;
        }
    if (x!=1) a[x]+=y;
}//质因数分解 
void qp(int t){
    if (t==1) return;
    qp(t/2);
    c=c*c;
    if (t%2) c=c*b;
}//快速次幂 
void print(bignum b){
    printf("%lld",b.a[b.a[0]]);
    for (int i=b.a[0]-1;i;i--) printf("%09lld",b.a[i]);
}
int main(){
    scanf("%d",&n);
    for (int i=1;i<=n;i++){
        scanf("%d",&d[i]);
        if (d[i]!=-1) s+=d[i]-1; else m++;
    }
    for (int i=2;i<=n-2;i++) chai(i,1);
    chai(m,n-2-s);
    for (int i=2;i<=n-2-s;i++) chai(i,-1);
    for (int i=1;i<=n;i++)
        if (d[i]!=-1)
            for (int j=2;j<d[i];j++) chai(j,-1);
    ans.a[0]=ans.a[1]=1;
    for (int i=1;i<=n;i++)
        if (a[i]>0){
            c.a[0]=b.a[0]=1;
            c.a[1]=b.a[1]=i;
            qp(a[i]);
            ans=ans*c;
        }
    print(ans);
}

 

bzoj1005: [HNOI2008]明明的烦恼


联系
我们