美文网首页
Xiangtan Invitation Contest 2017

Xiangtan Invitation Contest 2017

作者: evilgiven | 来源:发表于2017-07-18 15:38 被阅读0次
    0.png

    题目大概意思是给一个 [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;
    }
    
    

    相关文章

      网友评论

          本文标题:Xiangtan Invitation Contest 2017

          本文链接:https://www.haomeiwen.com/subject/ewkhkxtx.html