设 \(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