Description "奮戰三星期，造台電腦"。小W響應號召，花了三星期造了台文藝計算姬。文藝計算姬比普通電腦有更多的藝 術細胞。普通電腦能計算一個帶標號完全圖的生成樹個數，而文藝計算姬能計算一個帶標號完全二分圖的生成樹 個數。更具體地，給定一個一邊點數為n，另一邊點數為m，共有n*m條邊的 ...
Submit: 737 Solved: 402
[Submit][Status][Discuss]
Description
"奮戰三星期，造台電腦"。小W響應號召，花了三星期造了台文藝計算姬。文藝計算姬比普通電腦有更多的藝 術細胞。普通電腦能計算一個帶標號完全圖的生成樹個數，而文藝計算姬能計算一個帶標號完全二分圖的生成樹 個數。更具體地，給定一個一邊點數為n，另一邊點數為m，共有n*m條邊的帶標號完全二分圖K_{n,m}，計算姬能快 速算出其生成樹個數。小W不知道計算姬算的對不對，你能幫助他嗎？
Input
僅一行三個整數n,m,p，表示給出的完全二分圖K_{n,m} 1 <= n,m,p <= 10^18
Output
僅一行一個整數，表示完全二分圖K_{n,m}的生成樹個數，答案需要模p。
Sample Input
2 3 7Sample Output
5HINT
Source
演算法1
結合MatrixTree定理打表或者歸納證明
演算法2
根據prufe
r因為prufer序列對應著唯一的一棵樹，問題轉為計算有多少合法的prufer序列。
“一種生成Prufer序列的方法是迭代刪點，直到原圖僅剩兩個點。”根據prufer序列的性質，最後剩下的兩個點一定有一條邊，在二分圖中有連邊的兩點一定處於不同集合。在刪除時會“移去所有葉子節點（度為1的頂點）中標號最小的頂點和相連的邊，並把與它相鄰的點的編號加入Prufer序列中”，每刪除一個點都需要將與它連邊的點加到prufer序列中，而二分圖中的邊兩端的點一定屬於不同集合，那麼A集合有n-1個點被刪除，也就是說B集合中的數需要被加入n-1次，共有$m^n−1$種可能；B集合同理，有m-1個點被刪除，也就是說A集合中的數需要被加入m-1次，共有$n^m−1$種可能。
兩種情況相乘得到答案為$n^{m−1}∗m^{n−1}$
#include<cstdio> #include<cstring> #include<algorithm> #define int long long using namespace std; const int MAXN=1e6+10,INF=1e4+10; inline int read() { char c=getchar();int x=0,f=1; while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();} while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();} return x*f; } int fastmul(int a,int p,int mod) { int base=0; while(p) { if(p&1) base=(base+a)%mod; a=(a+a)%mod; p>>=1; } return base; } int fastpow(int a,int p,int mod) { int base=1; while(p) { if(p&1) base=fastmul(base,a,mod)%mod; a=fastmul(a,a,mod)%mod; p>>=1; } return base; } main() { int N=read(),M=read(),P=read(); printf("%lld",fastmul(fastpow(N,M-1,P),fastpow(M,N-1,P),P)%P); return 0; }
