3.27 算法补全：行列式（扩展）

标签：海森堡 补全 多项式 det 行列式 3.27 DP lambda

行列式 Ex

海森堡矩阵行列式

上海森堡阵是满足其次对角线下的值都为 \(0\)，即只有 \(i\le j+1\) 处的 \(a_{i,j}\) 的矩阵。

上海森堡阵的行列式可以 \(O(n^2)\) DP 求解，因为在这个矩阵中选择一个不含 \(0\) 的排列，一定满足会形成如下形式：\(x,1,2,\dots,x-1\mid y,x+1,\dots,y-1\mid\dots\)，即若干个区间的环拼接起来。于是我们直接 DP，\(f_i\) 表示 \([1,i]\) 构成若干个环的方案权值和，那么 \(f_i=\sum_{j}(-1)^{j-i}f_{j}g_{j+1,i}\)，其中 \(g_{l,r}=a_{l,r}\prod_{i=l+1}^{r} a_{i,i-1}\).

特征多项式

对于方阵 \(A\)，定义其特征多项式 \(p_A(\lambda)=\det(\lambda I_n-A)\)。

对于方阵 \(A,B\)，若存在初等可逆矩阵 \(P\) 满足 \(B=PAP^{-1}\)，那么称 \(A,B\) 互为相似矩阵。

相似矩阵特征多项式相同。

证明：

\[p_B(\lambda)=\det(\lambda I-PAP^{-1})=\det(\lambda PIP^{-1}-PAP^{-1})=\det(P(\lambda I-A)P^{-1})\\=\det(P)\det(\lambda I-A)\det(P^{-1})=p_A(\lambda) \]

任意一个方阵，都可以找到一个海森堡矩阵与其相似。

消元方法：考虑我们在消元（构造 \(P\)）的同时，算上 \(P^{-1}\) 带来的贡献。我们进行消元的时候会进行行变换：\(R_i:=R_i+kR_{j}\)，那么其对应右乘 \(P^{-1}\) 带来的变换就是列变换 \(C_j:=C_j-kC_i\)；类似的，交换 \(R_i,R_j\) 的操作，对应右乘 \(P^{-1}\) 带来的变换就是交换 \(C_i,C_j\)。我们若怀着消成海森堡阵的目标，容易发现列变换不会造成什么影响。

于是普通方阵求特征多项式只需要先变消成一个上海森堡阵，然后再 DP 出其特征多项式即可。

对于上海森堡阵，就很好做了，直接对上述 DP 进行一个修改，得到 \(p_i=\lambda p_{i-1}-\sum_j p_jg_{j+1,i}\)。

https://judge.yosupo.jp/submission/199210

\(A+Bz\) 行列式

首先我们可以用求特征多项式一样的方法求出 \(\det(A+I_nz)\)（代 \(A_{i,j}=-A_{i,j}\) 就是特征多项式）。

于是对于 \(A+Bz\)，考虑把 \(B\) 消元成 \(I_n\)。但是有可能 \(B\) 不满秩，那么就无法消成 \(I_n\)。这种情况下，考虑一个操作：将这一行乘上 \(z\)，即把这一行从 \(R_{A}+R_{B}z\) 变成 \(R_Az+R_Bz^2\)，由于 \(R_B\) 处满足该行该列为 \(0\) 所以不产生贡献，所以就变成了 \(R_Az\)，然后再进行消元。然后我们不断这样做，直到 \(B_{i,i}\neq 0\)，或者乘的 \(z\) 的个数 \(>n\)。

https://qoj.ac/submission/368908

范德蒙德行列式

考虑方阵 \(a_{i,j}=x_i^j\)，\(0\le i,j<n\)，那么其行列式为 \(\prod_{0\le i<j<n} (x_j-x_i)\)。

可以归纳得证。

神秘题 1

（忘了出处的模拟赛）给定常数 \(c\)，矩阵 \(a\) 满足对于 \(i=j\) 有 \(a_{i,j}=1\)，\(i\neq j\) 时 \(a_{i,j}=c\times [i\not \mid j]\)，求其行列式。\(n\le 10^{11}\)。

注意到一个下三角全为 \(c\)，所以考虑直接差分，\(a_{i,j}=a_{i,j}-a_{i-1,j}\)，得到一个上海森堡阵。然后我们直接 DP，得到 \(f_i=\sum_{j<i}f_{j-1}(c-1)^{i-j}(-1)^{i-j}ca_{j,i}+f_{i-1}(1-c)\)，令 \(h_i=f_i(c-1)^{-i}(-1)^i\)，那么有 \(h_i=\sum_{j<i}ca_{j,i}h_{j-1}+h_{i-1}\)。令 \(g_{i}=h_i-h_{i-1}\)，那么 \(g_i=\sum_{j<i}ca_{j,i}h_{j-1}\)，带入题目中的矩阵得到 \(g_i=c\sum_{j<i}([j\not\mid i]-[j-1\not\mid i])h_{j-1}=c(h_{i-2}-\sum_{j<i-1}[j\not\mid i]g_j)=c\sum_{j\mid i,j<i-1}g_j\)，可以发现 \(g\) 是一个积性函数，并且是 \([0,c,c,\dots]\) 的迪利克雷逆，所以直接杜教筛即可。

神秘题 2

目前隐藏

标签：海森堡,补全,多项式,det,行列式,3.27,DP,lambda
From： https://www.cnblogs.com/TetrisCandy/p/18100030