Description
"奋战三星期,造台计算机"。小W响应号召,花了三星期造了台文艺计算姬。文艺计算姬比普通计算机有更多的艺
术细胞。普通计算机能计算一个带标号完全图的生成树个数,而文艺计算姬能计算一个带标号完全二分图的生成树 个数。更具体地,给定一个一边点数为n,另一边点数为m,共有n*m条边的带标号完全二分图K_{n,m},计算姬能快 速算出其生成树个数。小W不知道计算姬算的对不对,你能帮助他吗?Input
仅一行三个整数n,m,p,表示给出的完全二分图K_{n,m}
1 <= n,m,p <= 10^18Output
仅一行一个整数,表示完全二分图K_{n,m}的生成树个数,答案需要模p。
Sample Input
2 3 7
Sample Output
5
Solution
答案为 \(n^{m-1}+m^{n-1}\)
这个可用矩阵树定理证出具体参考:Code
直接快速幂会爆long long
//By Menteur_Hxy#include#include #include #include #include #include #define F(i,a,b) for(register int i=(a);i<=(b);i++)using namespace std;typedef long long LL;LL read() { LL x=0,f=1; char c=getchar(); while(!isdigit(c)) {if(c=='-')f=-f;c=getchar();} while(isdigit(c)) x=(x<<1)+(x<<3)+c-48,c=getchar(); return x*f;}LL n,m,MOD;LL mul(LL a,LL b) { LL t=0; if(a >=1; } return t;}LL qpow(LL a,LL b) { LL t=1; a%=MOD; while(b) { if(b&1) t=mul(t,a); a=mul(a,a); b>>=1; } return t;}int main() { n=read(),m=read(),MOD=read(); printf("%lld",mul(qpow(n,m-1),qpow(m,n-1))%MOD); return 0;}