高斯消元模板

SPOJ-DETER3

  • 高斯消元对常数取模模板
  • 给出一个矩阵求行列式
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    #include <iostream>
    #include <algorithm>
    #include <string.h>
    using namespace std;
    const int inf = 0x3f3f3f3f;
    const int maxn = 205;
    #define ll long long 
    ll b[maxn][maxn];
    ll n, mod;
    // 学过线代都知道求行列式的方法之一就是化成上\下三脚矩阵,对角线元素乘积是行列式值
    ll determina(int n) {
    	ll res = 1;
    	for (int i = 1; i <= n; i++) {
    		if (!b[i][i]) { //若果对角线元素为0,把此行都一都移到下一行去
    			bool flag = false;
    			for (int j = i + 1; j <= n; j++) { //从i+1行开始找i列中的第一个不为0的元素，与现在的行交换
    				if (b[j][i]) {//找到了该列不为0的元素,
    					flag = 1; //标记,交换
    					for (int k = i; k <= n; k++) swap(b[i][k], b[j][k]);
    					res = -res;// 换行系数变为负数
    					break; //退出.
    				}
    			}
    			if (!flag) return 0; //这一行全部为0,行列式值为0
    		}

    		for (int j = i + 1; j <= n; j++) {
    			while (b[j][i]) { //从下面的行找一个不为0的元素与第i行进行消元
    				ll t = b[i][i] / b[j][i];
    				for (int k = i; k <= n; k++) {
    					b[i][k] = (b[i][k] - t * b[j][k]) % mod;
    					swap(b[i][k], b[j][k]);//消元后,把0的行换到下面来。
    				}
    				res = -res;
    			}
    		}
    		res *= b[i][i];//对角线元素相乘
    		res %= mod;
    	}
    	return (res + mod) % mod;
    }

    int main() {
    	//	freopen("a.txt","r",stdin);
    	while (scanf("%lld%lld", &n, &mod) != EOF) {
    		memset(b, 0, sizeof b);
    		for (int i = 1; i <= n; i++)
    			for (int j = 1; j <= n; j++) {
    				scanf("%lld", &b[i][j]);
    				b[i][j] = b[i][j] % mod;
    			}
    		printf("%lld\n", determina(n));
    	}
    	return 0;
    }