Current position : 首页 >> prufer编码

  • 「BZOJ1005」[HNOI2008] 明明的烦恼

    「BZOJ1005」[HNOI2008] 明明的烦恼

    Description自从明明学了树的结构,就对奇怪的树产生了兴趣......给出标号为1到N的点,以及某些点最终的度数,允许在任意两点间连线,可产生多少棵度数满足要求的树?Input第一行为N(0<N<=1000),接下来N行,第i+1行给出第i个节点的度数Di,如果对度数不要求,则输入-1Output一个整数,表示不同的满足要求的树的个数,无解输出0SampleInput31-1-1SampleOutput2HINT 两棵树分别为1-2-3;1-3-2 题解该题运用到了...

    62014年5月30日10,702高精度,prufer编码,排列组合

  • 「BZOJ1211」[HNOI2004] 树的计数

    「BZOJ1211」[HNOI2004] 树的计数

    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输出满足条件的树有多少棵。SampleInput42121SampleOutpu...

    02014年5月30日5,050prufer编码,排列组合

  • 「BZOJ1430」小猴打架

    「BZOJ1430」小猴打架

    Description一开始森林里面有N只互不相识的小猴子，它们经常打架，但打架的双方都必须不是好朋友。每次打完架后，打架的双方以及它们的好朋友就会互相认识，成为好朋友。经过N-1次打架之后，整个森林的小猴都会成为好朋友。现在的问题是，总共有多少种不同的打架过程。比如当N=3时，就有{1-2,1-3}{1-2,2-3}{1-3,1-2}{1-3,2-3}{2-3,1-2}{2-3,1-3}六种不同的打架过程。Input一个整数N。Output一行，方案数mod9999991。Sample...

    02014年4月3日3,455prufer编码