P11057 诈骗题 题解
l1ng21y12026
·
·
题解
只需基础行列式变换，计算量超级超级小，这么巧妙的证明真的不看看吗 OvO
注意到操作次数 =n+m-1，每次选择行 / 列。不难追忆到“重塑矩阵”使用图论转化。
将行、列看作点，操作 (x,y,R) 则连边 x\to y+n，操作 (x,y,C) 则连边 y+n\to x。
手玩一下不难发现，操作集合与有标号外向树满足其二分图染色后各 n,m 个点的方案双射。
证明：任何合法操作都可以生成这样的树。任意这样的树也可以从叶子开始依次还原回操作序列。故两者双射。
考虑计数。
定根 n+m 种，现在问题为：求完全二分图 K_{n,m} 的有标号生成树个数。
矩阵树经典问题，答案为 n^{m-1}m^{n-1}。
证明：
根据矩阵树定理：L(G)=D(G)-A(G)，G 的生成树方案数为：
\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=n，设其为 L'(G)，我们对 L'(G) 进行行列式变换：
L' = \begin{bmatrix}
m I_n & -J_{n \times (m-1)} \\
-J_{(m-1) \times n} & n I{m-1}
\end{bmatrix}
其中 I_n 是 n 行 n 列的单位矩阵，J_{n\times m} 是 n\times m 的全 1 矩阵。
对 L' 进行行变换：将前 n 行的 \frac{1}{m} 倍加到后 m-1 行。
\begin{bmatrix}
m I_n & -J_{n \times (m-1)} \\
0 & B
\end{bmatrix}
其中 B = n I_{m-1} - \frac{n}{m} J_{m-1}。
由于这是上三角矩阵，根据行列式定义：
\det A=\sum_{p} (-1)^{\pi (p)}\prod_{i=1}^n A_{i,p_i}
我们惊喜地发现，前 n 行 n 列一定有 p_i=i，否则为 0。于是可以提出 m^n ，只需要计算 \det B。
先化简 B：
\det(B) = n^{m-1} \cdot \det\left( I{m-1} - \frac{1}{m} J{m-1} \right)
$$
\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\sim n-1$ 行加到第 $1$ 行。
$$
\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}
$$
行变换，将第 $1$ 行加到第 $2\sim n-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}
$$
好了，这又是一个上三角矩阵，它的行列式即为 $\frac 1m$。
合起来，$Ans=\frac 1m \times n^{m-1}\times m^{n}=n^{m-1}\times n^{n-1}$。证毕。