首页 > 代码库 > [bzoj1005][HNOI2008][明明的烦恼] (高精度+prufer定理)
[bzoj1005][HNOI2008][明明的烦恼] (高精度+prufer定理)
Description
自从明明学了树的结构,就对奇怪的树产生了兴趣......给出标号为1到N的点,以及某些点最终的度数,允许在
任意两点间连线,可产生多少棵度数满足要求的树?
Input
第一行为N(0 < N < = 1000),
接下来N行,第i+1行给出第i个节点的度数Di,如果对度数不要求,则输入-1
Output
一个整数,表示不同的满足要求的树的个数,无解输出0
Sample Input
31-1-1
Sample Output
2HINT
两棵树分别为1-2-3;1-3-2
Solution
填昨天的坑
根据prufer定理，用排列组合推出ans=(n-2)!/[(D1-1)!(D2-1)!···(Dk-1)!left!] * m^left
其中left=(n-2)-(D1-1)-(D2-1)-···-(Dk-1)
哦，还要注意特判，当无解时，高精度数组长度为0，直接输出0就行了
PoPoQQQ的代码很优雅
Code：
#include <stdio.h>#include <memory.h>#define ll long longstruct num { int top; ll x[500]; num(ll a=0) { memset(x,0,sizeof x ); top=1; x[1]=a; } num operator*(const num b) { num tmp; for(int i=1; i<=top; i++) for(int j=1; j<=b.top; j++) tmp.x[i+j-1]+=x[i]*b.x[j], tmp.x[i+j]+=tmp.x[i+j-1]/100000000, tmp.x[i+j-1]%=100000000; tmp.top=top+b.top; if(!tmp.x[tmp.top]) tmp.top--; return tmp; } }ans(1);void Q_pow(int x,int p) { num tmp(x); for(;p;p>>=1,tmp=tmp*tmp) if(p&1) ans=ans*tmp; }int n,m,lef,cnt[1010];void factorZ(int x,int d) { for(int i=2;i*i<=x;i++) while(!(x%i)) cnt[i]+=d, x/=i; if(x^1)cnt[x]+=d; }int main() { scanf("%d",&n); lef=n-2; for(int i=2;i<=lef;i++) factorZ(i,1); for(int i=1;i<=n;i++) { int x; scanf("%d",&x); if(~x) { if(x>1) { lef-=x-1; for(int i=2;i<=x-1;i++) factorZ(i,-1); } } else ++m; } for(int i=2;i<=lef;i++) factorZ(i,-1); factorZ(m,lef); for(int i=2;i<=n;i++) if(cnt[i]) Q_pow(i,cnt[i]); printf("%lld",ans.x[ans.top]); for(int i=ans.top-1;i;i--) printf("%08lld",ans.x[i]); return 0; }
[bzoj1005][HNOI2008][明明的烦恼] (高精度+prufer定理)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。