BZOJ 4766 - 文艺计算姬

#数学 #Matrix-Tree 定理 #行列式
Published on 2017-03-20

题目地址

描述

给定一个带标号完全二分图 Kn,mK_{n,m}，计算其生成树个数。

分析

答案为：

nm−1mn−1 n^{m - 1}m^{n - 1}

证明：根据 Matrix-Tree 定理，Kn,mK_{n, m} 的生成树数量等于其基尔霍夫矩阵去掉一行一列所得行列式的绝对值。

∣m0⋯0−1−1⋯−10m⋯0−1−1⋯−1⋮⋮⋱⋮⋮⋮⋱⋮00⋯m−1−1⋯−1−1−1⋯−1n0⋯0−1−1⋯−10n⋯0⋮⋮⋱⋮⋮⋮⋱⋮−1−1⋯−100⋯n∣ \left\vert\begin{matrix} 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{matrix}\right\vert

注意上面有 nn 行，而下面只有 m−1m - 1 行（我们去掉了一行一列）。我们用前 nn 行来消去左下角的 −1-1：

∣m0⋯0−1−1⋯−10m⋯0−1−1⋯−1⋮⋮⋱⋮⋮⋮⋱⋮00⋯m−1−1⋯−100⋯0n−nm−nm⋯−nm00⋯0−nmn−nm⋯−nm⋮⋮⋱⋮⋮⋮⋱⋮00⋯0−nm−nm⋯n−nm∣ \left\vert\begin{matrix} 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\\ 0 & 0 & \cdots & 0 & n - \frac n m & - \frac n m &\cdots & - \frac n m\\ 0 & 0 & \cdots & 0 & - \frac n m& n - \frac n m &\cdots & - \frac n m\\ \vdots &\vdots &\ddots &\vdots & \vdots &\vdots &\ddots &\vdots\\ 0 & 0 & \cdots & 0 & - \frac n m & - \frac n m & \cdots & n - \frac n m \end{matrix}\right\vert

设

D1=∣m0⋯00m⋯0⋮⋮⋱⋮00⋯m∣,D2=∣n−nm−nm⋯−nm−nmn−nm⋯−nm⋮⋮⋱⋮−nm−nm⋯n−nm∣ D_1 = \left\vert\begin{matrix} m & 0 &\cdots & 0\\ 0 & m & \cdots & 0\\ \vdots &\vdots &\ddots &\vdots\\ 0&0&\cdots & m \end{matrix}\right\vert, D_2 = \left\vert\begin{matrix} n - \frac n m & - \frac n m &\cdots & - \frac n m\\ - \frac n m& n - \frac n m &\cdots & - \frac n m\\ \vdots &\vdots &\ddots &\vdots\\ - \frac n m & - \frac n m & \cdots & n - \frac n m \end{matrix}\right\vert

由于右下角都是 00，此时行列式的值转化为 D1D2D_1D_2。

显然 D1=nmD_1 = n^m，我们考虑 D2D_2：

∣n−nm−nm⋯−nm−nmn−nm⋯−nm⋮⋮⋱⋮−nm−nm⋯n−nm∣ \left\vert\begin{matrix} n - \frac n m & - \frac n m &\cdots & - \frac n m\\ - \frac n m& n - \frac n m &\cdots & - \frac n m\\ \vdots &\vdots &\ddots &\vdots\\ - \frac n m & - \frac n m & \cdots & n - \frac n m \end{matrix}\right\vert

从第二行开始，每一行都加到第一行：

D2=∣n−(m−1)nmn−(m−1)nm⋯n−(m−1)nm−nmn−nm⋯−nm⋮⋮⋱⋮−nm−nm⋯n−nm∣ D_2 = \left\vert\begin{matrix} n - (m - 1)\frac n m & n - (m - 1)\frac n m &\cdots & n - (m - 1)\frac n m\\ - \frac n m& n - \frac n m &\cdots & - \frac n m\\ \vdots &\vdots &\ddots &\vdots\\ - \frac n m & - \frac n m & \cdots & n - \frac n m \end{matrix}\right\vert

可提出常数：

D2=(n−(m−1)nm)∣11⋯1−nmn−nm⋯−nm⋮⋮⋱⋮−nm−nm⋯n−nm∣ D_2 = \left(n - (m - 1)\frac n m\right)\left\vert\begin{matrix} 1 & 1 &\cdots & 1\\ - \frac n m & n - \frac n m &\cdots & - \frac n m\\ \vdots &\vdots &\ddots &\vdots\\ - \frac n m & - \frac n m & \cdots & n - \frac n m \end{matrix}\right\vert

将第一行乘 nm\frac n m 加到下面每一行：

D2=(n−(m−1)nm)∣11⋯10n⋯0⋮⋮⋱⋮00⋯n∣=(n−(m−1)nm)⋅nm−2=nm⋅nm−2 D_2 = \left(n - (m - 1)\frac n m\right)\left\vert\begin{matrix} 1 & 1 &\cdots & 1\\ 0 & n &\cdots & 0\\ \vdots &\vdots &\ddots &\vdots\\ 0 & 0 & \cdots & n \end{matrix}\right\vert = \left(n - (m - 1)\frac n m\right)\cdot n^{m - 2} = \frac n m\cdot n^{m - 2}

化简得：

D2=nm−1m D_2 = \frac {n^{m - 1}} m

所以：

D1D2=mnnm−1m=nm−1mn−1 D_1D_2 = m^n\frac {n^{m - 1}} m = n^{m - 1}m^{n - 1}

即得证。

代码

//  Created by Sengxian on 2017/3/20.
//  Copyright (c) 2017年 Sengxian. All rights reserved.
//  BZOJ 4766 Matrix-Tree + 行列式化简
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
ll n, m, mod;

inline ll modMul(ll a, ll b) {
    ll res = 0;
    while (b) {
        if (b & 1) (res += a) %= mod;
        (a <<= 1) %= mod;
        b >>= 1;
    }
    return res;
}

inline ll modPow(ll a, ll b) {
    ll res = 1;
    while (b) {
        if (b & 1) res = modMul(res, a);
        a = modMul(a, a);
        b >>= 1;
    }
    return res;
}

int main() {
    scanf("%lld%lld%lld", &n, &m, &mod);
    printf("%lld\n", modMul(modPow(n, m - 1), modPow(m, n - 1)));
    return 0;
}
BZOJ 3817 - Sum