题目:
给定一个一边点数为\(n\),另一边点数为\(m\),共有\(n*m\)条边的带标号完全二分图\(K_{n,m}\)
计算其生成树个数
\(n,m,p \leq 10^{18} ,p为模数\)
题解:
构建出基尔霍夫矩阵.
找到n-1阶主子式后将所有的行直接加到第一行上.
可以得到前n个是1,后m个是0的一个行向量.
然后用这个行向量消剩下的n-m-2行.
很容易得到一个上三角矩阵.
将对角线上的值乘起来即为答案.
\(ans = n^{m-1}m^{n-1}\)
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
inline void read(ll &x){
x=0;static char ch;bool flag = false;
while(ch=getchar(),ch<'!');if(ch == '-') ch=getchar(),flag = true;
while(x=(x<<1)+(x<<3)+ch-'0',ch=getchar(),ch>'!');if(flag) x=-x;
}
#define rg register int
#define rep(i,a,b) for(rg i=(a);i<=(b);++i)
#define per(i,a,b) for(rg i=(a);i>=(b);--i)
ll mod;
inline ll mul(ll x,ll y){
ll t = x*y - (ll)( (long double)x/mod*y + 0.5)*mod;
return t < 0 ? t + mod : t;
}
inline ll qpow(ll x,ll p){
ll ret = 1LL;
for(;p;p>>=1,x=mul(x,x)) if(p&1) ret=mul(ret,x);
return ret;
}
int main(){
ll n,m;read(n);read(m);read(mod);
printf("%lld\n",mul(qpow(m,n-1),qpow(n,m-1)));
return 0;
}