bzoj4766 文艺计算姬

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

正解：矩阵树定理+快速幂+黑科技乘法。
很水的一道题。。用矩阵树定理打表以后就发现$Ans=m^{n-1}*n^{m-1}$，然后可以先快速幂然后黑科技乘法解决。

 //It is made by wfj_2048~

 #include <algorithm>

 #include <iostream>

 #include <complex>

 #include <cstring>

 #include <cstdlib>

 #include <cstdio>

 #include <vector>

 #include <cmath>

 #include <queue>

 #include <stack>

 #include <map>

 #include <set>

 #define inf (1<<30)

 #define eps (1e-9)

 #define il inline

 #define RG register

 #define ll long long

 #define File(s) freopen(s".in","r",stdin),freopen(s".out","w",stdout)

 using namespace std;

 ll n,m,p;

 il ll mul(RG ll a,RG ll b){

     return (ll)(a*b-(ll)((long double)a/p*b+0.5)*p+p)%p;

 }

 il ll qpow(RG ll a,RG ll b){

     RG ll ans=;

     while (b){

     if (b&) ans=mul(ans,a);

     a=mul(a,a),b>>=;

     }

     return ans;

 }

 int main(){

     File("ji");

     cin>>n>>m>>p;

     RG ll a=qpow(n%p,m-),b=qpow(m%p,n-);

     printf("%lld",mul(a,b));

     return ;

 }

秒客网