【学习笔记】[ABC323G] Inversion of Tree

学习笔记】[ABC323G] Inversion of Tree"/>

【学习笔记】[ABC323G] Inversion of Tree

前置知识：矩阵树定理，特征多项式

省流：板子缝合题。可以复习一下线性代数的基本知识。

定义 P u > P v P_u>P_v Pu​>Pv​的边价值为 x x x， P u < P v P_u<P_v Pu​<Pv​的边价值为 1 1 1，那么我们要求一个矩阵 L L L的行列式中 x i x^i xi对应的系数。

暴力做法是 O ( n 4 ) O(n^4) O(n4)的。所以需要一点科技。

考虑特征多项式。对于一个 n × n n\times n n×n的矩阵 A A A，定义它的特征多项式为：

p A ( x ) = det ⁡ ( x I n − A ) p_A(x)=\operatorname{det}(xI_n-A) pA​(x)=det(xIn​−A)

其中 I n I_n In​是一个 n n n阶的单位矩阵，最后的 p A ( x ) p_A(x) pA​(x)是一个 n n n次多项式。

如果一个矩阵次对角线下方的位置全部都是 0 0 0，那么把其称为上海森堡矩阵。

任意 n n n级矩阵的特征多项式都能在 O ( n 3 ) O(n^3) O(n3)的时间复杂度内求出，方法：

1.1 1.1 1.1 利用相似矩阵特征行列式相同的性质将给定矩阵消成上海森堡矩阵

这是因为对于初等可逆矩阵 P P P，有：

det ⁡ ( x I n − A ) = det ⁡ ( x I n − P A P − 1 ) \operatorname{det}(xI_n-A)=\operatorname{det}(xI_n-PAP^{-1}) det(xIn​−A)=det(xIn​−PAP−1)

这个东西 好像见过，当时不知道有啥用。。。（其实用处还挺大的，可以加速 矩阵快速幂，但是手算的部分挺难的。。。）

考虑高斯消元的三个操作：

• 交换两行
• 将第 i i i行的 k k k倍加到第 j j j行上
• 将第 i i i行的数乘上 k k k

它们都能写成一个矩阵 P P P。也就是说，每次消元的过程可以看成左乘上矩阵 P P P，而 P − 1 P^{-1} P−1不难手算得到，并且右乘上 P − 1 P^{-1} P−1等价于是对列进行操作，因此在消元的过程中，当我们对行进行操作时，要同时对列执行其共轭操作。

1.2 1.2 1.2 使用行列式展开定理递推计算它的特征多项式

记 p i ( x ) p_i(x) pi​(x)表示左上角 i × i i\times i i×i的矩阵对应的特征多项式。则递推式 可以一通手算得到 ：

p i ( x ) = x ⋅ p i − 1 ( x ) − ∑ m = 1 i A m , i ( ∏ j = m + 1 i A j , j − 1 ) p m − 1 ( x ) p_i(x)=x\cdot p_{i-1}(x)-\sum_{m=1}^iA_{m,i}(\prod_{j=m+1}^iA_{j,j-1})p_{m-1}(x) pi​(x)=x⋅pi−1​(x)−m=1∑i​Am,i​(j=m+1∏i​Aj,j−1​)pm−1​(x)

特别的， p 0 ( x ) = 1 p_0(x)=1 p0​(x)=1。

对于这道题，考虑将 L L L分解成：

L = A + x B L=A+xB L=A+xB

然后同时对 A , B A,B A,B进行消元操作，即：

L ′ = A ′ + x I L'=A'+xI L′=A′+xI

最后套用上述做法即可。

注意到第一步过程中如果有一列被消完了那么就将这一列乘上 x x x（等价于将 A A A的这一列搬到 B B B上），如果乘 x x x的次数 > n >n >n就寄了。

因为都是板子，所以建议多看一下代码。

注意行和列都要进行操作。

复杂度 O ( n 3 ) O(n^3) O(n3)。

#include<bits/stdc++.h>
#define ll long long
#define pb push_back
#define fi first
#define se second
using namespace std;
const int N=505;
const int mod=998244353;
int n,p[N];
ll A[N][N],B[N][N],dp[N][N],res[N];
ll fpow(ll x,ll y=mod-2){ll z(1);for(;y;y>>=1){if(y&1)z=z*x%mod;x=x*x%mod;}return z;
}
void add(ll &x,ll y){x=(x+y)%mod;
}
int main(){ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);cin>>n;for(int i=0;i<n;i++)cin>>p[i];for(int i=0;i<n;i++){for(int j=i+1;j<n;j++){if(p[i]>p[j]){A[i][i]++,A[j][j]++,A[i][j]--,A[j][i]--;}else{B[i][i]++,B[j][j]++,B[i][j]--,B[j][i]--;}}}n--;int mul=0;ll coef=1;for(int i=0;i<n;i++){for(int j=i;j<n;j++){if(A[j][i]!=0){swap(A[i],A[j]);swap(B[i],B[j]);if(i!=j)coef*=-1;break;}}while(A[i][i]==0){for(int j=0;j<n;j++){A[j][i]=B[j][i];B[j][i]=0;}mul++;if(mul>n){for(int i=0;i<=n;i++)cout<<0<<"\n";return 0;}for(int j=0;j<i;j++){if(A[j][i]!=0){ll x=A[j][i];for(int k=0;k<n;k++){add(A[k][i],-A[k][j]*x);add(B[k][i],-B[k][j]*x);}}}for(int j=i;j<n;j++){if(A[j][i]!=0){swap(A[i],A[j]);swap(B[i],B[j]);}if(i!=j){coef*=-1;}break;}}ll inv=fpow(A[i][i]);coef=coef*A[i][i]%mod;for(int j=0;j<n;j++){A[i][j]=A[i][j]*inv%mod;B[i][j]=B[i][j]*inv%mod;}for(int j=i+1;j<n;j++){if(A[j][i]!=0){ll x=A[j][i];for(int k=0;k<n;k++){add(A[j][k],-x*A[i][k]);add(B[j][k],-x*B[i][k]);}}}for(int j=i+1;j<n;j++){if(A[i][j]!=0){ll x=A[i][j];for(int k=0;k<n;k++){add(A[k][j],-x*A[k][i]);add(B[k][j],-x*B[k][i]);}}}}for(int i=0;i<n-1;i++){int p=-1;for(int j=i+1;j<n;j++){if(B[j][i]!=0){p=j;break;}}if(p==-1)continue;if(p!=i+1){for(int j=0;j<n;j++)swap(B[i+1][j],B[p][j]);for(int j=0;j<n;j++)swap(B[j][i+1],B[j][p]);}for(int j=i+2;j<n;j++){if(B[j][i]!=0){ll x=B[j][i]*fpow(B[i+1][i])%mod;for(int k=0;k<n;k++)add(B[j][k],-B[i+1][k]*x);for(int k=0;k<n;k++)add(B[k][i+1],B[k][j]*x);}}}for(int i=0;i<n;i++){for(int j=0;j<n;j++){B[i][j]=-B[i][j];}}dp[0][0]=coef;for(int i=0;i<n;i++){for(int j=0;j<n;j++){dp[i+1][j+1]=dp[i][j];}ll v=1;for(int j=i;j>=0;j--){for(int k=0;k<=i+1;k++){add(dp[i+1][k],-v*dp[j][k]%mod*B[j][i]);}if(j)v=v*B[j][j-1]%mod;}}for(int i=mul;i<=n;i++)res[i-mul]=dp[n][i];for(int i=0;i<=n;i++)cout<<(res[i]+mod)%mod<<" ";
}