题目概述

求二分图 $K_{n,m}$ 的生成树个数。

解题报告

我骗我自己：$A+B=d(dA+dB)$ ，导致我做不出来。

二分图的基尔霍夫矩阵的一个主子式长这样（上面 $n$ 行，下面 $m-1$ 行）：

$$ \begin{bmatrix} m&0&\cdots&0&-1&-1&\cdots&-1\\ 0&m&\cdots&0&-1&-1&\cdots&-1\\ \vdots&\vdots&\ddots&\vdots&\vdots&\vdots&\ddots&\vdots\\ 0&0&\cdots&m&-1&-1&\cdots&-1\\ -1&-1&\cdots&-1&n&0&\cdots&0\\ -1&-1&\cdots&-1&0&n&\cdots&0\\ \vdots&\vdots&\ddots&\vdots&\vdots&\vdots&\ddots&\vdots\\ -1&-1&\cdots&-1&0&0&\cdots&n\\ \end{bmatrix} $$

我是这样消的（当然方法多样）：先把最后 $m-2$ 行都减去上面一行，这样下面 $m-2$ 行就只剩下了一堆 $0$ 还有 $-n,n$ 。然后把第 $n+1$ 行乘上 $m$ ，提取 $1\over m$ 到前面，再把 $1\sim n$ 行全部往第 $n+1$ 行上加一遍，第 $n+1$ 行就变成了前面 $0$ ，一个 $n(m-1)$ 和后面 $-n$ 。此时再把第 $n+2$ 行乘上 $m-1$ ，提取 $1\over m-1$ 到前面，加上 $n+1$ 行，第 $n+2$ 行就变成了前面 $0$ ，一个 $n(m-2)$ 和后面 $-n$ ，以此类推往下搞就可以消成对角矩阵啦。

贡献为 ${m^n\cdot n^{m-1}\cdot(m-1)!\over m!}=m^{n-1}\cdot n^{m-1}$ 。

示例程序

推式子20min，打代码2min，呵呵。

#include<cstdio>
using namespace std;
typedef long long LL;typedef long double DB;

LL n,m,MOD;

inline LL Mul(LL x,LL y) {return ((x*y-(LL)((DB)x/MOD*y)*MOD)%MOD+MOD)%MOD;}
inline LL Pow(LL w,LL b) {LL s=1;for (;b;b>>=1,w=Mul(w,w)) if (b&1) s=Mul(s,w);return s;}
int main(){
    freopen("program.in","r",stdin);freopen("program.out","w",stdout);
    scanf("%lld%lld%lld",&n,&m,&MOD);printf("%lld\n",Mul(Pow(n,m-1),Pow(m,n-1)));return 0;
}