求助帖：关于此题求行列式时找非零元素的疑惑

P5296 [北京省选集训2019] 生成树计数

Lumos壹玖贰壹 @ 2022-01-04 08:57:09

~~萌新刚学oi~~

可能问题描述不清，重新描述问题：\ 高斯消元消当前列时首先向下要找到一个非零元素，若不在当前行要行变换，若没非零元素直接返回0

这题找非零元素为什么只判多项式常数项系数非零啊，而且s_r_f大佬貌似都没找？

是因为这题保证是完全图吗?那联合省选的作业题为什么也只判常数项系数？

by Lumos壹玖贰壹 @ 2022-01-04 09:04:42

@wangrx

by warzone @ 2022-01-04 09:28:34

@Lumos壹玖贰壹这种你应该直接问 @s_r_f

估计是数据太水...

by monstersqwq @ 2022-01-05 01:43:02

@Lumos壹玖贰壹因为非零元素主要是求逆吧但是常数项不为0的项已经可以求逆了（？

by _l_l_ @ 2023-01-30 19:37:34

@Lumos壹玖贰壹好消息是，如果你在高斯消元前判断了图联通，由矩阵树定理，每一次消元都可以找到一个零次项非零的多项式

当然没找是可以卡的（

by danielqf @ 2024-10-06 12:02:21

好像不用找也是对的。

考虑只保留常数项时高斯消元的过程

\begin{aligned} &\left|\begin{matrix} n-1 & -1 & -1 & \cdots & -1 \\ -1 & n-1 & -1 & \cdots & -1 \\ -1 & -1 & n-1 & \cdots & -1 \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ -1 & -1 & -1 & \cdots & n-1 \\ \end{matrix}\right|_{n-1}\\ =&\left|\begin{matrix} n-1 & -1 & -1 & \cdots & -1 \\ 0 & \frac{n(n-2)}{n-1} & \frac{-n}{n-1} & \cdots & \frac{-n}{n-1} \\ 0 & \frac{-n}{n-1} & \frac{n(n-2)}{n-1} & \cdots & \frac{-n}{n-1} \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ 0 & \frac{-n}{n-1} & \frac{-n}{n-1} & \cdots & \frac{n(n-2)}{n-1} \\ \end{matrix}\right|_{n-1}\\ =&(n-1)\left|\begin{matrix} \frac{n(n-2)}{n-1} & \frac{-n}{n-1} & \cdots & \frac{-n}{n-1} \\ \frac{-n}{n-1} & \frac{n(n-2)}{n-1} & \cdots & \frac{-n}{n-1} \\ \vdots & \vdots & \ddots & \vdots \\ \frac{-n}{n-1} & \frac{-n}{n-1} & \cdots & \frac{n(n-2)}{n-1} \\ \end{matrix}\right|_{n-2}\\ =&(n-1)\left(\frac n{n-1}\right)^{n-2}\left|\begin{matrix} n-2 & -1 & \cdots & -1 \\ -1 & n-2 & \cdots & -1 \\ \vdots & \vdots & \ddots & \vdots \\ -1 & -1 & \cdots & n-2 \\ \end{matrix}\right|_{n-2} \end{aligned}

不会在对角线上消出 0.