menu ZigZagK的博客
account_circle

正在努力加载中QAQ

[矩阵树定理]BZOJ4766【文艺计算姬】题解
apps BZOJ
local_offer 查看标签
comment 0 条评论

题目概述

求二分图 $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;
}
版权声明:本博客所有文章除特别声明外,均采用 CC BY 4.0 CN协议 许可协议。转载请注明出处!
名称不能为空
email
邮箱不能为空,请填写正确格式
link
网址请用http://或https://开头
message
评论不能为空
资瓷Markdown和LaTex数学公式
sentiment_very_satisfied
keyboard_arrow_up