bzoj1430

这道题只是给bzoj1005做一个铺垫
这里介绍了一个叫prufer编码的东西，就是
给定一棵带标号的无根树，找出编号最小的叶子节点，写下与它相邻的节点的编号，
然后删掉这个叶子节点。反复执行这个操作直到只剩两个节点为止。
这个编码有几个重要的性质
1. 每棵树都唯一对应一个prufer编码
2. 每一个prufer编码都唯一对应一棵树
3. 树上每个点的度数-1=这个点在数列出现的次数
所以用这个解决完全图生成树个数就很显然了，答案是n^(n-2)

 const mo=;

 var c:array[..] of longint;

     i,j,p,b:longint;

     ans,n:int64;

 begin

   readln(n);

   j:=;

   b:=n-;

   while b<> do

   begin

     inc(j);

     c[j]:=b mod ;

     b:=b div ;

   end;

   ans:=;

   for i:=j downto  do

   begin

     ans:=sqr(ans) mod mo;

     if c[i]= then ans:=ans*int64(n) mod mo;

   end;

   for i:= to n- do

     ans:=ans*int64(i) mod mo;

   writeln(ans);

 end.

巴特西

bzoj1430

最新文章

热门文章