Time Limit:?1 Sec??Memory Limit:?128 MB
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 7

Sample Output

5

HINT

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;
}

?

轉載于:https://www.cnblogs.com/zwfymqz/p/8456205.html

總結

以上是生活随笔為你收集整理的BZOJ4766: 文艺计算姬的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。