专栏文章

P11057 诈骗题 题解

ll1ng21y12026
P11057题解参与者 2已保存评论 6

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
6 条
当前快照
1 份
快照标识符
@mind41vd
此快照首次捕获于
2025/12/02 00:27
3 个月前
此快照最后确认于
2025/12/02 00:27
3 个月前
查看原文
Kn,m=nm−1mn−1K_{n,m}=n^{m-1}m^{n-1} 矩阵树定理的证明过程。
只需基础行列式变换，计算量超级超级小，这么巧妙的证明真的不看看吗 OvO
注意到操作次数 =n+m−1=n+m-1，每次选择行 / 列。不难追忆到“重塑矩阵”使用图论转化。
将行、列看作点，操作 (x,y,R)(x,y,R) 则连边 x→y+nx\to y+n，操作 (x,y,C)(x,y,C) 则连边 y+n→xy+n\to x。
手玩一下不难发现，操作集合与有标号外向树满足其二分图染色后各 n,mn,m 个点的方案双射。
证明：任何合法操作都可以生成这样的树。任意这样的树也可以从叶子开始依次还原回操作序列。故两者双射。
考虑计数。
定根 n+mn+m 种，现在问题为：求完全二分图 Kn,mK_{n,m} 的有标号生成树个数。
矩阵树经典问题，答案为 nm−1mn−1n^{m-1}m^{n-1}。
证明：
根据矩阵树定理：L(G)=D(G)−A(G)L(G)=D(G)-A(G)，GG 的生成树方案数为：
det⁡L(G)(1,2,…,i−1,i+1,…n1,2,…,i−1,i+1,…n)\det L(G) \begin{pmatrix} 1,2,\dots,i-1,i+1,\dots n\\ 1,2,\dots,i-1,i+1,\dots n \end{pmatrix}
取 i=ni=n，设其为 L′(G)L'(G)，我们对 L′(G)L'(G) 进行行列式变换：
L′=[mIn−Jn×(m−1)−J(m−1)×nnIm−1]L' = \begin{bmatrix} m I_n & -J_{n \times (m-1)} \\ -J_{(m-1) \times n} & n I{m-1} \end{bmatrix}
其中 InI_n 是 nn 行 nn 列的单位矩阵，Jn×mJ_{n\times m} 是 n×mn\times m 的全 11 矩阵。
对 L′L' 进行行变换：将前 nn 行的 1m\frac{1}{m} 倍加到后 m−1m-1 行。
[mIn−Jn×(m−1)0B]\begin{bmatrix} m I_n & -J_{n \times (m-1)} \\ 0 & B \end{bmatrix}
其中 B=nIm−1−nmJm−1B = n I_{m-1} - \frac{n}{m} J_{m-1}。
由于这是上三角矩阵，根据行列式定义：
det⁡A=∑p(−1)π(p)∏i=1nAi,pi\det A=\sum_{p} (-1)^{\pi (p)}\prod_{i=1}^n A_{i,p_i}
我们惊喜地发现，前 nn 行 nn 列一定有 pi=ip_i=i，否则为 00。于是可以提出 mnm^n ，只需要计算 det⁡B\det B。
先化简 BB：
det⁡(B)=nm−1⋅det⁡(Im−1−1mJm−1)\det(B) = n^{m-1} \cdot \det\left( I{m-1} - \frac{1}{m} J{m-1} \right)
det⁡\det 里面的矩阵长这样（是 (n−1)×(n−1)(n-1)\times (n-1) 的）：
[1−1m−1m⋯−1m−1m1−1m⋯−1m⋮⋮⋱⋮−1m−1m⋯1−1m]\begin{bmatrix} 1 - \frac{1}{m} & -\frac{1}{m} & \cdots & -\frac{1}{m} \\ -\frac{1}{m} & 1 - \frac{1}{m} & \cdots & -\frac{1}{m} \\ \vdots & \vdots & \ddots & \vdots \\ -\frac{1}{m} & -\frac{1}{m} & \cdots & 1 - \frac{1}{m} \end{bmatrix}
行变换，将 2∼n−12\sim n-1 行加到第 11 行。
[1m1m⋯1m−1m1−1m⋯−1m⋮⋮⋱⋮−1m−1m⋯1−1m]\begin{bmatrix} \frac{1}{m} & \frac{1}{m} & \cdots & \frac{1}{m} \\ -\frac{1}{m} & 1 - \frac{1}{m} & \cdots & -\frac{1}{m} \\ \vdots & \vdots & \ddots & \vdots \\ -\frac{1}{m} & -\frac{1}{m} & \cdots & 1 - \frac{1}{m} \end{bmatrix}
行变换，将第 11 行加到第 2∼n−12\sim n-1 行。
[1m1m⋯1m01⋯0⋮⋮⋱⋮00⋯1]\begin{bmatrix} \frac{1}{m} & \frac{1}{m} & \cdots & \frac{1}{m} \\ 0 & 1 & \cdots & 0 \\ \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & \cdots & 1 \end{bmatrix}
好了，这又是一个上三角矩阵，它的行列式即为 1m\frac 1m。
合起来，Ans=1m×nm−1×mn=nm−1×nn−1Ans=\frac 1m \times n^{m-1}\times m^{n}=n^{m-1}\times n^{n-1}。证毕。

评论

共 6 条评论，欢迎与作者交流。

正在加载评论...