高斯消元板子

$n\cdot n$矩阵$a$求逆元, 存放在a[1...n][n+1...2n], 若无逆元则throw

void Gauss() {
	REP(i,1,n) {
		REP(j,n+1,2*n) a[i][j] = 0;
		a[i][i+n] = 1;
	}
	REP(i,1,n) {
		int p = i;
		while (!a[p][i]&&p<=n) ++p;
		if (p>n) throw;
		if (p!=i) REP(j,1,2*n) swap(a[p][j],a[i][j]);
		if (a[i][i]!=1) {
			ll in = inv(a[i][i]);
			REP(j,i,2*n) a[i][j]=a[i][j]*in%P;
		}
		REP(j,1,n) if (j!=i&&a[j][i]) {
			ll t = P-a[j][i];
			REP(k,i,2*n) a[j][k]=(a[j][k]+t*a[i][k])%P;
		}
	}
}

$n\cdot m$增广矩阵$a$化为行最简形, $r$为矩阵的秩

void Gauss() {
	int r = 1;
	REP(i,1,n) {
		int p = r;
		while (!a[p][i]&&p<=n) ++p;
		if (p>n) continue;
		if (p!=i) REP(j,i,m) swap(a[p][j],a[i][j]);
		if (a[i][i]!=1) {
			ll in = inv(a[i][i]);
			REP(j,i,m) a[i][j]=a[i][j]*in%P;
		}
		REP(j,1,n) if (j!=i&&a[j][i]) {
			ll t = P-a[j][i];
			REP(k,i,m) a[j][k]=(a[j][k]+t*a[i][k])%P;
		}
	}
}