Random Walk 2
【2.4】Gauss-Jordan消元法求矩陣的逆
高斯消元求矩陣的逆，伴隨單位矩陣一起消元即可。
[A,I]→[I,A?1][\text A,\text I]\to [\text I,\text A^{-1}][A,I]→[I,A?1]
移項變形，后就是個矩陣的逆，為啥賽時不寫？？？草（一種植物）
#include<bits/stdc++.h>
using namespace std
;
using ll
=long long;
const ll mod
=998244353;
const int N
=310;
int W
[N
][N
];
ll P
[N
][N
],P0
[N
][N
];
ll I
[N
][N
],A
[N
][N
];
int n
;
ll
qmi(ll a
,ll b
)
{ll v
=1;while(b
){if(b
&1) v
=v
*a
%mod
;b
>>=1;a
=a
*a
%mod
;}return v
;
}
void Inv()
{for(int c
=1,r
=1;c
<=n
;c
++){int t
=r
;for(int i
=c
;i
<=n
;i
++)if(abs(P
[i
][c
])>abs(P
[t
][c
])) t
=i
;if(P
[t
][c
]==0) continue;for(int j
=1;j
<=n
;j
++) {swap(I
[t
][j
],I
[r
][j
]);swap(P
[t
][j
],P
[r
][j
]);}ll inv
=qmi(P
[r
][c
],mod
-2);for(int j
=1;j
<=n
;j
++){I
[r
][j
]=I
[r
][j
]*inv
%mod
;P
[r
][j
]=P
[r
][j
]*inv
%mod
;}for(int i
=1;i
<=n
;i
++)if(i
!=r
&&P
[i
][c
]!=0){ll v
=P
[i
][c
];for(int j
=1;j
<=n
;j
++){I
[i
][j
]=(I
[i
][j
]-v
*I
[r
][j
]%mod
+mod
)%mod
;P
[i
][j
]=(P
[i
][j
]-v
*P
[r
][j
]%mod
+mod
)%mod
;}}r
++;}}
void Mul()
{for(int i
=1;i
<=n
;i
++) for(int j
=1;j
<=n
;j
++) A
[i
][j
]=0;for(int i
=1;i
<=n
;i
++)for(int j
=1;j
<=n
;j
++) for(int k
=1;k
<=n
;k
++) A
[i
][j
]=(A
[i
][j
]+I
[i
][k
]*P0
[k
][j
]%mod
)%mod
;
}
int main()
{ios
::sync_with_stdio(false);cin
.tie(nullptr);cout
.tie(nullptr);int Tc
=1;cin
>>Tc
;while(Tc
--){cin
>>n
;for(int i
=1;i
<=n
;i
++) for(int j
=1;j
<=n
;j
++) cin
>>W
[i
][j
];for(int i
=1;i
<=n
;i
++) for(int j
=1;j
<=n
;j
++) P
[i
][j
]=P0
[i
][j
]=0,I
[i
][j
]=(i
==j
);for(int i
=1;i
<=n
;i
++){ll tot
=0;for(int j
=1;j
<=n
;j
++) tot
+=W
[i
][j
];ll inv
=qmi(tot
,mod
-2);for(int j
=1;j
<=n
;j
++){if(i
!=j
) P
[i
][j
]=1ll*W
[i
][j
]*inv
%mod
;else P0
[i
][j
]=1ll*W
[i
][j
]*inv
%mod
;}for(int j
=1;j
<=n
;j
++){P
[i
][j
]=mod
-P
[i
][j
];if(i
==j
) P
[i
][j
]=1;}}Inv();Mul();for(int i
=1;i
<=n
;i
++) for(int j
=1;j
<=n
;j
++) cout
<<A
[i
][j
]<<" \n"[j
==n
];}return 0;
}
總結
以上是生活随笔為你收集整理的2021“MINIEYE杯”中国大学生算法设计超级联赛（5）Random Walk 2（推式子+矩阵逆+矩阵乘）的全部內容，希望文章能夠幫你解決所遇到的問題。
如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。
