生活随笔
收集整理的這篇文章主要介紹了
bzoj1430
小編覺得挺不錯的,現在分享給大家,幫大家做個參考.
這道題只是給bzoj1005做一個鋪墊
這里介紹了一個叫prufer編碼的東西，就是
給定一棵帶標號的無根樹，找出編號最小的葉子節(jié)點，寫下與它相鄰的節(jié)點的編號，
然后刪掉這個葉子節(jié)點。反復執(zhí)行這個操作直到只剩兩個節(jié)點為止。
這個編碼有幾個重要的性質
1.?每棵樹都唯一對應一個prufer編碼
2.?每一個prufer編碼都唯一對應一棵樹
3.?樹上每個點的度數-1=這個點在數列出現的次數
所以用這個解決完全圖生成樹個數就很顯然了，答案是n^(n-2)
1 const mo=
9999991;
2 var c:
array[
0..
100]
of longint;
3 i,j,p,b:longint;
4 ans,n:int64;
5
6 begin
7 readln(n);
8 j:=
0;
9 b:=n-
2;
10 while b<>
0 do
11 begin
12 inc(j);
13 c[j]:=b
mod 2;
14 b:=b
div 2;
15 end;
16 ans:=
1;
17 for i:=j
downto 1 do
18 begin
19 ans:=sqr(ans)
mod mo;
20 if c[i]=
1 then ans:=ans*int64(n)
mod mo;
21 end;
22 for i:=
1 to n-
1 do
23 ans:=ans*int64(i)
mod mo;
24 writeln(ans);
25 end.
26
27 View Code ?
轉載于:https://www.cnblogs.com/phile/p/4473067.html
總結
以上是生活随笔為你收集整理的bzoj1430的全部內容，希望文章能夠幫你解決所遇到的問題。
如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。
