nyoj--127--星際之門（一）（生成樹的數量）

星際之門（一）

時間限制：3000?ms ?|? 內存限制：65535?KB

難度：3

描述

公元3000年，子虛帝國統領著N個星系，原先它們是靠近光束飛船來進行旅行的，近來，X博士發明了星際之門，它利用蟲洞技術，一條蟲洞可以連通任意的兩個星系，使人們不必再待待便可立刻到達目的地。

帝國皇帝認為這種發明很給力，決定用星際之門把自己統治的各個星系連結在一起。

可以證明，修建N-1條蟲洞就可以把這N個星系連結起來。

現在，問題來了，皇帝想知道有多少種修建方案可以把這N個星系用N-1條蟲洞連結起來？

?

輸入

第一行輸入一個整數T,表示測試數據的組數(T<=100)
每組測試數據只有一行，該行只有一個整數N，表示有N個星系。(2<=N<=1000000)

輸出

對于每組測試數據輸出一個整數，表示滿足題意的修建的方案的個數。輸出結果可能很大，請輸出修建方案數對10003取余之后的結果。

樣例輸入

2
3
4

樣例輸出

3
16

來源

[張云聰]原創

上傳者

張云聰

我也不清楚為毛線這一道題為什麼會出現在圖論中，大概是證明過程，參考大神的證明：

簡單點說就是：
一一對應法：
假定T是其中一棵樹，樹葉中有標號最小者，設為a1，a1的鄰接點為b1，從圖中消去a1點
和邊(a1, b1).b1點便成為消去后余下的樹T1的頂點.在余下的樹T1中尋找標號最小的樹葉，設
為a2，a2的鄰接點為b2，從T1中消去a2及邊(a2, b2).如此步驟繼續n-2次，直到最后剩下一條
邊為止.于是一棵樹T對應一序列
b1,b2,…,b[n-2]
恢復樹T：
序列I 1,2,…n
序列II b1,b2,…,b[n-2]
在I中找出第一個不出現在II中數，顯然是a1，連接邊(a1, b1)，在I中消去a1，在II中消
去b1.如此步驟重復n-2次，序列I中兩個數，構成最后一條邊.

以下是來自Matirx67的blog.

ayley公式是說，一個完全圖K_n有n^(n-2)棵生成樹，換句話說n個節點的帶標號的無根樹有n^(n-2)個。Cayley公式的一個非常簡單的證明，證明依賴于Prüfer編碼，它是對帶標號無根樹的一種編碼方式。
給定一棵帶標號的無根樹，找出編號最小的葉子節點，寫下與它相鄰的節點的編號，然后刪掉這個葉子節點。反復執行這個操作直到只剩兩個節點為止。由于節點數n>2的樹總存在葉子節點，因此一棵n個節點的無根樹唯一地對應了一個長度為n-2的數列，數列中的每個數都在1到n的范圍內。下面我們只需要說明，任何一個長為n-2、取值范圍在1到n之間的數列都唯一地對應了一棵n個節點的無根樹，這樣我們的帶標號無根樹就和Prüfer編碼之間形成一一對應的關系，Cayley公式便不證自明了。
看到這，我建議自己劃一劃，結果就出來了（這句話是我的建議，非Matrix67原文）。
注意到，如果一個節點A不是葉子節點，那么它至少有兩條邊；但在上述過程結束后，整個圖只剩下一條邊，因此節點A的至少一個相鄰節點被去掉過，節點A的編號將會在這棵樹對應的Prüfer編碼中出現。反過來，在Prüfer編碼中出現過的數字顯然不可能是這棵樹（初始時）的葉子。于是我們看到，沒有在Prüfer編碼中出現過的數字恰好就是這棵樹（初始時）的葉子節點。找出沒有出現過的數字中最小的那一個（比如④），它就是與Prüfer編碼中第一個數所標識的節點（比如③）相鄰的葉子。接下來，我們遞歸地考慮后面n-3位編碼（別忘了編碼總長是n-2）：找出除④以外不在后n-3位編碼中的最小的數（左圖的例子中是⑦），將它連接到整個編碼的第2個數所對應的節點上（例子中還是③）。再接下來，找出除④和⑦以外后n-4位編碼中最小的不被包含的數，做同樣的處理……依次把③⑧②⑤⑥與編碼中第3、4、5、6、7位所表示的節點相連。最后，我們還有①和⑨沒處理過，直接把它們倆連接起來就行了。由于沒處理過的節點數總比剩下的編碼長度大2，因此我們總能找到一個最小的沒在剩余編碼中出現的數，算法總能進行下去。這樣，任何一個Prüfer編碼都唯一地對應了一棵無根樹，有多少個n-2位的Prüfer編碼就有多少個帶標號的無根樹。

一個有趣的推廣是，n個節點的度依次為D1, D2, …, Dn的無根樹共有(n-2)! / [ (D1-1)!(D2-1)!..(Dn-1)! ]個，因為此時Prüfer編碼中的數字i恰好出現Di-1次。

#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
#define M 10003
long long mod(int a,int b,int c)
{int t=1;if(b==0)return 1;if(b==1)return a%c;t=mod(a,b>>1,c);t=t*t%c;if(b&1)t=t*a%c;return t;
}
int main()
{int t;scanf("%d",&t);while(t--){int m;scanf("%d",&m);long long s=mod(m,m-2,M);printf("%lld\n",s);}return 0;
}