$\det(A+Bx)$
2022/1/16 6:06:45
本文主要是介绍$\det(A+Bx)$,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
设 \(A,B\) 为 \(n\times n\) 的域上矩阵,\(x\) 为不定元,\(O(n^3)\) 时间复杂度求出 \(\det(A+Bx)\)。
\(\det(A+Ix)\)
发现 \(\det(A+Ix)=\det(M(A+Ix)M^{-1})=\det(MAM^{-1}+Ix)\),其中 \(M\) 为任意可逆矩阵。也就意味着可以将 \(A\) 相似成上海森堡矩阵(即 \(\forall i>j+1,A_{i,j}=0\)),具体可以考虑当 \(M\) 为初等变换时 \(MAM^{-1}\) 的效果。然后对于上海森堡矩阵,使 \(\prod A_{i,\sigma(i)}\neq0\) 的排列 \(\sigma\) 一定是由若干个 \((i,j+1,j+2,\ldots,i-1)\) 的区间拼起来,于是容易 \(O(n^3)\) 递推求出其行列式。
\(\det(A+Bx)\)
考虑先把 \(B\) 高斯消元成 \(I\)。但注意消元到第 \(i\) 行时,可能出现这一行的 \(B\) 均为 \(0\) 的情况。此时可以将这一行乘上 \(x\) 然后将前 \(i-1\) 列位置上的 \(B\) 用前 \(i-1\) 行的主元削掉,最后在答案中除 \(x\)。如果此时 \(B\) 仍均为 \(0\),就不停重复这个过程,但如果最后除的 \(x\) 次数 \(>n\) 就可以直接结束,此时答案必为 \(0\)。
code
(在 \(\mathbb F_{998244353}\) 下)
#include<bits/stdc++.h> #define P 998244353 #define N 505 inline int fmo(int x){ return x+((x>>31)&P); } inline int fp(int x,int k=P-2){ int res=1; for(;k;k>>=1,x=1ll*x*x%P) if(k&1) res=1ll*res*x%P; return res; } int n,a[N][N],b[N][N]; int f[N][N]; int main(){ scanf("%d",&n); for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) scanf("%d",&a[i][j]); for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) scanf("%d",&b[i][j]); int flg=1,t=0; for(int i=1;i<=n;i++){ if(!b[i][i]) for(int j=i+1;j<=n;j++) if(b[j][i]){ flg=fmo(-flg); std::swap(a[i],a[j]),std::swap(b[i],b[j]); break; } if(!b[i][i]) for(int j=i+1;j<=n;j++) if(b[i][j]){ flg=fmo(-flg); for(int k=1;k<=n;k++) std::swap(a[k][i],a[k][j]),std::swap(b[k][i],b[k][j]); break; } for(;!b[i][i]&&t<n;t++){ for(int j=1;j<=n;j++) b[i][j]=a[i][j],a[i][j]=0; for(int j=1;j<i;j++){ int tmp=1ll*b[i][j]*fp(b[j][j])%P; for(int k=1;k<=n;k++){ a[i][k]=fmo(a[i][k]-1ll*tmp*a[j][k]%P); b[i][k]=fmo(b[i][k]-1ll*tmp*b[j][k]%P); } } } int inv=fp(b[i][i]); for(int j=1;j<=n;j++) if(j!=i){ int tmp=1ll*b[j][i]*inv%P; for(int k=1;k<=n;k++){ a[j][k]=fmo(a[j][k]-1ll*tmp*a[i][k]%P); b[j][k]=fmo(b[j][k]-1ll*tmp*b[i][k]%P); } } } for(int i=1;i<=n;i++){ flg=1ll*flg*b[i][i]%P; int inv=fp(b[i][i]); for(int j=1;j<=n;j++) a[i][j]=1ll*a[i][j]*inv%P; } for(int i=1;i<n;i++){ if(!a[i+1][i]) for(int j=i+2;j<=n;j++) if(a[j][i]){ std::swap(a[i+1],a[j]); for(int k=1;k<=n;k++) std::swap(a[k][i+1],a[k][j]); break; } int inv=fp(a[i+1][i]); for(int j=i+2;j<=n;j++){ int tmp=1ll*a[j][i]*inv%P; for(int k=1;k<=n;k++) a[j][k]=fmo(a[j][k]-1ll*tmp*a[i+1][k]%P); for(int k=1;k<=n;k++) a[k][i+1]=fmo(a[k][i+1]+1ll*tmp*a[k][j]%P-P); } } f[0][0]=1; for(int i=1;i<=n;i++){ int tmp=1; for(int j=i;j;j--){ for(int k=0;k<=n;k++) f[i][k]=fmo(f[i][k]+1ll*((i-j)&1?fmo(-1):1)*f[j-1][k]%P*a[j][i]%P*tmp%P-P); tmp=1ll*tmp*a[j][j-1]%P; } for(int k=0;k<n;k++) f[i][k+1]=fmo(f[i][k+1]+f[i-1][k]-P); } for(int i=0;i<=n;i++) printf("%d ",i+t>n?0:int(1ll*flg*f[n][i+t]%P)); puts(""); }
\(\det(A+Bx+Cx^2)\)
https://codeforces.com/blog/entry/92248?#comment-818786
这篇关于$\det(A+Bx)$的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-11-23Springboot应用的多环境打包入门
- 2024-11-23Springboot应用的生产发布入门教程
- 2024-11-23Python编程入门指南
- 2024-11-23Java创业入门:从零开始的编程之旅
- 2024-11-23Java创业入门:新手必读的Java编程与创业指南
- 2024-11-23Java对接阿里云智能语音服务入门详解
- 2024-11-23Java对接阿里云智能语音服务入门教程
- 2024-11-23JAVA对接阿里云智能语音服务入门教程
- 2024-11-23Java副业入门:初学者的简单教程
- 2024-11-23JAVA副业入门:初学者的实战指南