0.png

題目大概意思是給一個 [n - 1] * [n] 的矩陣， 輸出一行 n 個數(shù)分別為原矩陣去掉第 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的逆所以很多循環(huán)是 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]);
        // 因為伴隨矩陣里面是代數(shù)余子式而且是按轉(zhuǎn)置的方式放置, 所以是第 n 列的值, 而且對于 (i + n) 為奇數(shù)的情況要取相反數(shù).
    }
    return 0;
}