不需要逆元的整数取模意义下的高斯消元

#include <bits/stdc++.h>

using namespace std; const int maxn = 1e2, mod = 1e9;

#define n N

int n, a[maxn][maxn]; inline int det()
{
	//cout << n << endl;
	int ans = 1; for (int i = 1; i <= n; i++)
	{
		for (int k = i + 1; k <= n; k++) while (a[k][i])
		{
			int d = a[i][i] / a[k][i];
			for (int j = i; j <= n; j++) a[i][j] = (a[i][j] - 1ll * d * a[k][j] % mod + mod) % mod;
			swap(a[i], a[k]), ans *= -1;
		}
		ans = (ans * 1ll * a[i][i]) % mod/*, cout << ans << endl*/;
	}
	return (ans % mod + mod) % mod;
}

#undef n

inline void add(int u, int v) { a[u][v]--, a[v][u]--, a[u][u]++, a[v][v]++; /*cout << ‘H‘ << u << v << endl;*/ }

char s[maxn][maxn]; int n, m, num[maxn][maxn]; int main()
{
	ios::sync_with_stdio(0), cin.tie(0), cin >> n >> m;
	for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) { cin >> s[i][j]; if (s[i][j] == ‘.‘) num[i][j] = ++N; }
	for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) if (num[i][j])
	{
		if (num[i][j + 1]) add(num[i][j], num[i][j + 1]); if (num[i + 1][j]) add(num[i][j], num[i + 1][j]);
	}
	N--, cout << det() << endl;
}

不需要逆元的整数取模意义下的高斯消元

原文：https://www.cnblogs.com/Linshey/p/14402694.html