上海森堡矩阵快速求解行列式

标签：dots 海森堡 color 矩阵 奇偶性 行列式

这是一个没啥用的小 trick，鉴于上下海森堡矩阵对称，此处只谈论上海森堡矩阵。

定义

海森堡阵（Hessenberg），是一个数学用语，对方阵 \(A\)，若 \(i＞j+1\) 时，有 \(A_{i,j}=0\) ，则称 \(A\) 是上海森堡阵。

行列式求解

考虑从行列式定义入手，即每行每列选择恰好一个元素，并乘以其奇偶性作为系数累加。
在第一行选择一列 \(j\)，并将第 \(j\) 列整体删掉，例如下面的一个矩阵：

\[A=\left(\begin{matrix}* & * & \color{red}{*} & *& \dots \\ \color{purple}{*} & * & X& *& \dots \\ & \color{blue}* & X& *& \dots \\ & & X& \color{green}*& \dots \\ & & & \color{green}*& \dots \\ & & & & \dots \end{matrix}\right) \]

如果选定了红色的列，那么蓝色位置的元素就必须被选中，进而选中紫色的位置，也就是说，第 \(j\) 列前的所有列都唯一确定了，对于第 \(j\) 列之后的列，只需考虑绿色部分的元素，这是一个 \((n-j)\cdot (n-j)\) 的子问题。

于是考虑 dp，记 \(f_n\) 表示后 \(n\) 行，后 \(n\) 列的行列式的值，转移需要考虑前 \(i\) 行列对排列奇偶性带来的变化，可以做到 \(O(n^2)\)，转移形如：\(f(n)=\sum_{i=0}^{n-1} f(i) d(n,i)\)，其中 \(d\) 为排列奇偶性带来的影响。

当上海森堡矩阵中的元素是一个低次多项式，我们可以证明，行列式的次数也不会超过元素的最高次数，于是转移仍然是 \(O(n)\)。

应用

ABC323G 待补。

标签：dots,海森堡,color,矩阵,奇偶性,行列式
From： https://www.cnblogs.com/Think927/p/17818662.html