首页 / JAVA / [BZOJ-1005&洛谷P2624][HNOI2008]明明的烦恼-【Purfer序列】py+java

[BZOJ-1005&洛谷P2624][HNOI2008]明明的烦恼-【Purfer序列】py+java

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了[BZOJ-1005&洛谷P2624][HNOI2008]明明的烦恼-【Purfer序列】py+java，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含2489字，纯文字阅读大概需要4分钟。

内容图文

题目链接：https://www.lydsy.com/JudgeOnline/problem.php?id=1005
洛谷：https://www.luogu.com.cn/problem/P2624
Time Limit: 1 Sec  Memory Limit: 162 MB
洛谷：时间限制1.00s  内存限制125.00MB

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

 

相较于04年的裸的Purfer序列，这题就不是那么裸了。

假设有k个是已知的度，那么根据Purfer序列的性质我们可以得到这k个已知度的答案：

技术分享图片

 那么该部分的答案应该为：

技术分享图片

 但由于purfer中有n-2个元素，那么这sum个元素的放置方法也有C（n-2,sum）种，即该部分的最终答案为：

技术分享图片

 然后就是剩下的了，剩下的有n-k个顶点，序列空余n-2-sum个位置，那么每个顶点有n-2-sum中放法，即有

技术分享图片种答案。

那么最终答案也就出来了：

技术分享图片

 

 emmmm，还是py一波+JAVA一波吧。。

以下是AC代码：（Python）

n=int(input())
a=[]
for i in range(n):
    a.append(int(input()))
sum=0;k=0
for i in range(n):
    if a[i]!=-1:
        sum+=a[i]-1
        k+=1
    elif a[i]==0:
        print(0)
        exit()

c=1
for i in range(n-2-sum+1,n-2+1):
    c*=i
for i in range(2,sum+1):
    c//=i

tot=1
f=[1]
for i in range(1,sum+1):
    tot*=i
    f.append(f[i-1]*i)
for i in range(n):
    if a[i]!=-1:
        tot//=f[a[i]-1]

last=1;
for i in range(n-2-sum):
    last*=(n-k)

print(c*tot*last)

 

（Java代码）：

                import
                 java.math.BigInteger;

                import
                 java.util.Scanner;


                class
                 Main {
    
                public
                static
                void
                 main(String[] args){
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        int a[]=newint[1005];
        int mark=0,sum=0,k=0;
        for (int i=1; i<=n; i++){
            a[i]=sc.nextInt();
            if (a[i]==0) mark=1;
            if (a[i]!=-1) {
                sum+=a[i]-1;k++;
            }
        }
        if (mark==1) {
            System.out.println("0");
            System.exit(0);
        }
        BigInteger s=new BigInteger("1");
        BigInteger num[]=new BigInteger[1005];
        num[0]=new BigInteger("0");
        int mx=n;
        if (sum>n) mx=sum;
        for (int i=1; i<=mx; i++)
            num[i]=num[i-1].add(new BigInteger("1"));
        for (int i=n-2; i>=n-2-sum+1; i--)
            s=s.multiply(num[i]);
        for (int i=2; i<=sum; i++)
            s=s.divide(num[i]);
        BigInteger tot=new BigInteger("1");
        for (int i=1; i<=sum; i++)
            tot=tot.multiply(num[i]);
        BigInteger f[]=new BigInteger[1050];
        f[0]=new BigInteger("1");
        for (int i=1; i<=n; i++)
            f[i]=f[i-1].multiply(num[i]);
        BigInteger cnt=new BigInteger("1");
        for (int i=1; i<=n; i++)
            if (a[i]!=-1)  cnt=cnt.multiply(f[a[i]-1]);
        BigInteger last=new BigInteger("0");
        for (int i=1; i<=n-k; i++) last=last.add(new BigInteger("1"));
        BigInteger tot_last=new BigInteger("1");
        for (int i=1; i<=n-2-sum; i++) tot_last=tot_last.multiply(last);
        System.out.println(s.multiply(tot.divide(cnt)).multiply(tot_last));
    }
}

 

 

 

 

原文：https://www.cnblogs.com/lonely-wind-/p/12189938.html

内容总结

以上是互联网集市为您收集整理的[BZOJ-1005&洛谷P2624][HNOI2008]明明的烦恼-【Purfer序列】py+java全部内容，希望文章能够帮你解决[BZOJ-1005&洛谷P2624][HNOI2008]明明的烦恼-【Purfer序列】py+java所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

扫描二维码推送至手机访问。

本文链接：https://qyyshop.com/info/1135050.html

来源：【匿名】