【学习笔记】[ABC323G] Inversion of Tree
已知nkessi一篇博客写50道题，而我的一篇博客写1道题，那么祂写博客的数量等价于我的多少篇博客？
省流：板子缝合题。可以复习一下线性代数的基本知识。
定义$P_u>P_v$的边价值为$x$，$P_u 暴力做法是$O(n^4)$的。所以需要一点科技。 考虑特征多项式。对于一个$n\times n$的矩阵$A$，定义它的特征多项式为： 其中$I_n$是一个$n$阶的单位矩阵，最后的$p_A(x)$是一个$n$次多项式。 如果一个矩阵次对角线下方的位置全部都是$0$，那么把其称为上海森堡矩阵。 任意$n$级矩阵的特征多项式都能在$O(n^3)$的时间复杂度内求出，方法： 这个东西 好像见过，当时不知道有啥用。。。（其实用处还挺大的，可以加速 矩阵快速幂，但是手算的部分挺难的。。。） 考虑高斯消元的三个操作： 它们都能写成一个矩阵$P$。也就是说，每次消元的过程可以看成左乘上矩阵$P$，而$P^{-1}$不难手算得到，并且右乘上$P^{-1}$等价于是对列进行操作，因此在消元的过程中，当我们对行进行操作时，要同时对列执行其共轭操作。 特别的，$p_0(x)=1$。 对于这道题，考虑将$L$分解成： 然后同时对$A,B$进行消元操作，即： 最后套用上述做法即可。 注意到第一步过程中如果有一列被消完了那么就将这一列乘上$x$（等价于将$A$的这一列搬到$B$上），如果乘$x$的次数$>n$就寄了。 因为都是板子，所以建议多看一下代码。 注意行和列都要进行操作。 复杂度$O(n^3)$。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
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