学习笔记】[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∑iAm,i(j=m+1∏iAj,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<<" ";
}
更多推荐
【学习笔记】[ABC323G] Inversion of Tree
发布评论