北京开发网站,企业查询系统官网天眼查,网络营销整合推广,动感网站模板Random Walk 2
【2.4】Gauss-Jordan消元法求矩阵的逆 高斯消元求矩阵的逆#xff0c;伴随单位矩阵一起消元即可。 [A,I]→[I,A−1][\text A,\text I]\to [\text I,\text A^{-1}][A,I]→[I,A−1] 移项变形#xff0c;后就是个矩阵的逆#xff0c;为啥赛时不写#xff1f;伴随单位矩阵一起消元即可。 [A,I]→[I,A−1][\text A,\text I]\to [\text I,\text A^{-1}][A,I]→[I,A−1] 移项变形后就是个矩阵的逆为啥赛时不写草一种植物
#includebits/stdc.h
using namespace std;
using lllong long;
const ll mod998244353;
const int N310;
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 v1;while(b){if(b1) vv*a%mod;b1;aa*a%mod;}return v;
}
void Inv()
{for(int c1,r1;cn;c){int tr;for(int ic;in;i)if(abs(P[i][c])abs(P[t][c])) ti;if(P[t][c]0) continue;for(int j1;jn;j) {swap(I[t][j],I[r][j]);swap(P[t][j],P[r][j]);}ll invqmi(P[r][c],mod-2);for(int j1;jn;j){I[r][j]I[r][j]*inv%mod;P[r][j]P[r][j]*inv%mod;}for(int i1;in;i)if(i!rP[i][c]!0){ll vP[i][c];for(int j1;jn;j){I[i][j](I[i][j]-v*I[r][j]%modmod)%mod;P[i][j](P[i][j]-v*P[r][j]%modmod)%mod;}}r;}}
void Mul() // I-1 × P0
{for(int i1;in;i) for(int j1;jn;j) A[i][j]0;for(int i1;in;i)for(int j1;jn;j) for(int k1;kn;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 Tc1;cinTc;while(Tc--){cinn;for(int i1;in;i) for(int j1;jn;j) cinW[i][j];for(int i1;in;i) for(int j1;jn;j) P[i][j]P0[i][j]0,I[i][j](ij);for(int i1;in;i){ll tot0;for(int j1;jn;j) totW[i][j];ll invqmi(tot,mod-2);for(int j1;jn;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 j1;jn;j){P[i][j]mod-P[i][j];if(ij) P[i][j]1;}}Inv();Mul();for(int i1;in;i) for(int j1;jn;j) coutA[i][j] \n[jn];}return 0;
}
