题目大概意思是给一个 [n - 1] * [n] 的矩阵, 输出一行 n 个数分别为原矩阵去掉第 i 行之后的子矩阵的 det.
如果每次去掉一列再高斯消元求子矩阵的 det 时间复杂的会到 O(n ^ 4),生成 n 个子矩阵每个子矩阵一次O(n ^ 3) 的高斯消元, 显然会TLE.
可以将原[n - 1] * [n] 的矩阵加一行补完成一个[n] * [n] 的方阵, 再通过求方阵的逆矩阵得到方阵的伴随矩阵得到结果, 这样就是 O(n ^ 3) 的
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int MAXN = 201;
const int P = 1e9 + 7;
long long Ori[MAXN][MAXN], Ret[MAXN][MAXN], M[MAXN][MAXN];
long long FastPowMod(long long x, long long p, long long MOD){ // 快速幂取模
long long res = 1;
while(p){
if(p & 1) res = res * x % MOD;
x = x * x % MOD;
p >>= 1;
}
return res;
}
void GetInverseMatrix(long long Ori[MAXN][MAXN], long long E[MAXN][MAXN], int n){
// 通过初等行变换求方阵 Ori 的 det(Ori) * Ori ^ -1
long long M[MAXN][MAXN], det = 1;
memset(E, 0, n * n * sizeof(long long));
// E 是 n 阶单位矩阵
for(int i = 1; i <= n; i++){
for(int j = 1; j <= n; j++) M[i][j] = ((Ori[i][j] % P) + P) % P, E[i][j] = 0;
E[i][i] = 1;
}
for(int i = 1; i <= n; i++){
int row = i;
for(int j = i; j <= n; j++) if(M[j][i]){row = j;break;}
// for(int j = i; j <= n; j++) if(M[j][i]) row = j; 本来是这样但是想不通为什么. 这里找 row 是防止 M[i][i] 为 0
if(row != i){
det *= -1;
swap(M[i], M[row]);
swap(E[i], E[row]);
}
det = M[i][i] * det % P;
long long inv = FastPowMod(M[i][i], P - 2, P);
for(int j = 1; j <= n; j++){
M[i][j] = inv * M[i][j] % P;
E[i][j] = inv * E[i][j] % P;
}
// 费马小定理, 将 M[i][i] 化为 1
for(int j = 1; j <= n; j++){
if(j == i) continue;
long long temp = M[j][i];
for(int k = 1; k <= n; k++){
M[j][k] = (M[j][k] - M[i][k] * temp % P + P) % P;
E[j][k] = (E[j][k] - E[i][k] * temp % P + P) % P;
}
}
}
// 以上为高斯消元求 det(Ori) 和 Ori 的逆部分, 因为是通过对 M|E 进行初等行变换来求 Ori的逆所以很多循环是 1 到 n 的
det = (det + P) % P;
for(int i = 1; i <= n; i++) for(int j = 1; j <= n; j++) E[i][j] = det * E[i][j] % P;
// 计算 det(Ori) 乘 Ori 的逆矩阵
}
int main()
{
int n;
while(scanf("%d", &n) != EOF){
for(int i = 1; i <= n - 1; i++){
for(int j = 1; j <= n; j++){
scanf("%I64d", &Ori[i][j]);
}
}
for(int j = 1; j <= n; j++) Ori[n][j] = 1;
GetInverseMatrix(Ori, Ret, n);
for(int i = 1; i <= n; i++) printf("%I64d%c", ((i + n) & 1 ? (P - Ret[i][n]) % P : Ret[i][n]), " \n"[i == n]);
// 因为伴随矩阵里面是代数余子式而且是按转置的方式放置, 所以是第 n 列的值, 而且对于 (i + n) 为奇数的情况要取相反数.
}
return 0;
}
网友评论