[人工智能]luogu P7776 【模板】特征多项式

https://www.luogu.com.cn/problem/P7776

众所周知，对于一个$n\times n$的矩阵$A$,它的特征多项式为$p(x)=DET(xI?A)$

有一条重要的性质

$DET(xI?A)=DET(xI?QA{Q}^{?1})$

证明:
$$\begin{gathered} DET(xI?QA{Q}^{?1}) \\ =DET(xQI{Q}^{?1}?QA{Q}^{?1}) \\ =DET(Q(xI?A)Q^{?1}) \\ =DET(Q)\times DET(xI?A)\times DET(Q^{?1}) \\ =DET(xI?A) \end{gathered}$$
我们称$QA{Q}^{?1}$为原矩阵$A$的相似矩阵

所以原矩阵和相似矩阵的特征多项式相同

因为一般的矩阵不一定都能相似对角化，但是都可以变成上海森堡矩阵（次对角线下全部是0）

我们考虑类高斯消元

高斯消元的过程相当于是把$A$变成$PA$

每一次操作可以看成左乘了一个矩阵$P$
要变成相似矩阵可以考虑在右边再乘一个$P^{?1}$

考虑这个矩阵$P$长啥样，假设要把第$i$行乘$k$加到第$j$行，那么就是一个单位矩阵，然后第$j$行，第$i$列是$k$

不难得到它的逆矩阵是第$j$行第$i$列为$?k$

对应为矩阵上就相当于是把第$j$列乘$?k$加到第$i$列上

注意交换两行的时候也要交换两列

然后就可以消成上海森堡矩阵了

然后考虑怎么求行列式
我们知道余子式与行列式的关系为

行列式等于它任意一行(列)的各元素与其对应的代数式余子式乘积之和

就是把某一行(列)的$a[i][j]?C[i][j]$求个和
$M[i][j]$表示去掉第$i$行第$j$列后剩下的矩阵
$C[i][j]=(?1{)}^{i+j}DET(M[i][j])$
设$p_i(x)$表示保留$A[1..i][1..i]$时的特征多项式

$p_0(x)=1$
假设已知了$p_{i?1}(x)$，新增第$i$行$i$列

我们按照最后一列展开，可以写为

$DET=(x?a[i][i])C[i][i]+a[i?1][i]C[i?1][i]+...$

第一项显然是$C[i][i]=p_{i?1}(x)$

考虑第二项，画出来之后发现最后一行只有一个$a[i][i?1]$按照它在展开为$a[i][i?1]C[i?2][i?2]$
就是$a[i][i?1]p_{i?2}(x)$
所以第二项为$a[i?1][i]a[i][i?1]p_{i?2}(x)$

同理可得
$$p_i(x)=(x?a[i][i])p_{i?1}(x)?\sum _{m=1}^{i?1}A[i?m][i](\prod _{j=i=m+1}^{i}a[j][j?1])p_{i?m?1}(x)$$
直接做就好了

code:

#include<bits/stdc++.h>
#define ll long long
#define N 505
#define mod 998244353
using namespace std;
ll qpow(ll x, ll y) {
    ll ret = 1;
    for(; y; y >>= 1, x = x * x % mod) if(y & 1) ret = ret * x % mod;
    return ret;
}
ll a[N][N], p[N][N];
int n;
void hesb(int n) {
    for(int i = 1; i < n; i ++) {
        int j = i + 1;
        for(int k = i + 1; k <= n; k ++) if(a[k][i]) j = k;
        if(j != i + 1) {
            swap(a[i + 1], a[j]); 
            for(int k = 1; k <= n; k ++) swap(a[k][i + 1], a[k][j]);
        }
        if(!a[i + 1][i]) continue; 
        for(int j = i + 2; j <= n; j ++) {
            ll t = a[j][i] * qpow(a[i + 1][i], mod - 2) % mod;
            for(int k = 1; k <= n; k ++) a[j][k] = (a[j][k] - t * a[i + 1][k] % mod + mod) % mod;
            for(int k = 1; k <= n; k ++) a[k][i + 1] = (a[k][i + 1] + t * a[k][j] % mod) % mod;
        } 
    }
}
int main() {
    scanf("%d", &n);
    for(int i = 1; i <= n; i ++)
        for(int j = 1; j <= n; j ++) scanf("%lld", &a[i][j]);
    hesb(n);
    // for(int i = 1; i <= n; i ++) {
    //     for(int j = 1; j <= n; j ++) printf("%lld ", a[i][j]); printf("\n");
    // }
    p[0][0] = 1;
    for(int i = 1; i <= n; i ++) {
        for(int j = 1; j <= n; j ++) p[i][j] = p[i - 1][j - 1];
        for(int j = 0; j <= n; j ++) p[i][j] = (p[i][j] - p[i - 1][j] * a[i][i] % mod + mod) % mod;
        for(int m = 1; m < i; m ++) {
            ll ret = a[i - m][i];
            for(int j = i - m + 1; j <= i; j ++) ret = ret * a[j][j - 1] % mod;
            for(int j = 0; j <= n; j ++) p[i][j] = (p[i][j] - ret * p[i - m - 1][j] % mod + mod) % mod;
        }
    }
    for(int i = 0; i <= n; i ++) printf("%lld ", p[n][i]);
    return 0;
}