Khử Gauss (Gaussian Elimination)
Giải hệ phương trình tuyến tính, tính hạng và định thức bằng biến đổi hàng. Trình bày cho số thực (chọn trụ lớn nhất), modulo số nguyên tố và GF(2) với cơ sở XOR.
Khử Gauss (Gaussian elimination) là thuật toán giải hệ phương trình tuyến tính ẩn bằng cách biến đổi sơ cấp trên hàng (đổi chỗ hai hàng, nhân một hàng với hằng số khác 0, cộng bội của hàng này vào hàng khác) cho tới khi ma trận có dạng bậc thang. Cùng một khung thuật toán cho ta: nghiệm của hệ (hoặc biết hệ vô nghiệm, vô số nghiệm), hạng của ma trận, định thức, ma trận nghịch đảo. Độ phức tạp , thực tế dùng được với tới khoảng (số thực, modulo) và lớn hơn nhiều trên nhờ bitset.
Trong competitive programming, khử Gauss xuất hiện trên ba "trường số": số thực (kỳ vọng, xác suất của bước đi ngẫu nhiên, mạch điện), modulo số nguyên tố (đếm theo modulo, định thức để đếm cây khung) và (bài bật tắt đèn, cơ sở XOR, XOR lớn nhất của tập con).
Ý tưởng / Trực giác
Vì sao biến đổi hàng không làm đổi tập nghiệm? Mỗi biến đổi sơ cấp đều khả nghịch: đổi chỗ thì đổi lại, nhân với thì nhân với , cộng lần hàng vào hàng thì trừ lại. Một nghiệm của hệ cũ thỏa mọi phương trình, nên thỏa cả các tổ hợp tuyến tính của chúng; điều ngược lại đúng nhờ tính khả nghịch. Vậy hệ mới và hệ cũ tương đương.
Thuật toán (bản Gauss-Jordan). Duyệt từng cột . Tìm trong các hàng chưa dùng một hàng có (gọi là trụ), đưa nó lên vị trí , rồi trừ bội thích hợp của hàng trụ khỏi mọi hàng khác để cột chỉ còn một số khác 0. Nếu cột không có trụ, ẩn tương ứng là ẩn tự do. Kết thúc, mỗi ẩn có trụ được đọc trực tiếp: .
Phân loại nghiệm. Gọi là số trụ (hạng của ).
- Có hàng mà vế trái toàn 0 nhưng vế phải khác 0 (dạng ): vô nghiệm.
- Ngược lại, nếu : nghiệm duy nhất.
- Ngược lại (): vô số nghiệm, có ẩn tự do. Trên trường hữu hạn phần tử, số nghiệm chính xác là .
Định thức. Đưa ma trận vuông về tam giác trên; định thức bằng tích các phần tử trên đường chéo, đổi dấu mỗi lần đổi chỗ hai hàng (cộng bội một hàng vào hàng khác không đổi định thức). Định thức bằng 0 khi và chỉ khi có cột không có trụ.
Ba trường số, ba cách chọn trụ.
- Số thực: phép chia cho số rất nhỏ khuếch đại sai số. Luôn chọn trụ có giá trị tuyệt đối lớn nhất trong cột (partial pivoting) và coi là 0. Nếu ma trận đối xứng xác định dương (ví dụ hệ kỳ vọng của bước đi ngẫu nhiên trên đồ thị vô hướng), khử không chọn trụ cũng ổn định.
- Modulo số nguyên tố : mọi số khác 0 có nghịch đảo (Fermat nhỏ: ), nên toàn bộ lý thuyết giữ nguyên; trụ chỉ cần khác 0, không có sai số.
- : cộng và trừ đều là XOR, nhân là AND, trụ chỉ cần là bit 1. Một hàng là một số nguyên (hoặc
bitset), khử cả hàng bằng một phép XOR. Trường hợp đặc biệt quan trọng là cơ sở XOR: chèn từng số vào một bảngbasis[b](vector có bit cao nhất là ), mỗi lần chèn là một bước khử. Tập các XOR của mọi tập con chính là không gian sinh bởi cơ sở, có đúng phần tử.
Vì sao tham lam trên cơ sở XOR cho giá trị lớn nhất? Trong cơ sở, các vector có bit cao nhất đôi một khác nhau. Duyệt bit từ cao xuống: quyết định lấy basis[b] chỉ ảnh hưởng bit và các bit thấp hơn, và các vector đứng sau không thể chạm bit . Vậy để bit bằng 1 khi có thể là tối ưu, và điều kiện (r ^ basis[b]) > r kiểm tra đúng việc đó.
Ví dụ chạy tay
Giải hệ trên số thực:
Ma trận mở rộng và ba lượt khử (chọn trụ có giá trị lớn nhất, đánh dấu [ ]):
ban đầu: sau cột 0 (trụ -3, hàng 2 lên đầu):
[ 2 1 -1 | 8 ] [ [-3] -1 2 | -11 ]
[ -3 -1 2 | -11 ] [ 0 1/3 1/3 | 2/3 ]
[ -2 1 2 | -3 ] [ 0 5/3 2/3 | 13/3 ]
sau cột 1 (trụ 5/3, đổi 2 hàng): sau cột 2 (trụ 1/5):
[ -3 0 12/5 | -42/5 ] [ -3 0 0 | -6 ]
[ 0 [5/3] 2/3 | 13/3 ] [ 0 5/3 0 | 5 ]
[ 0 0 1/5 | -1/5 ] [ 0 0 [1/5] | -1/5 ]
Ở cột 0, lớn nhất nên hàng 2 được đưa lên đầu; ở cột 1, giữa và ta chọn và đổi chỗ hai hàng dưới. Đọc nghiệm:
| Ẩn | Hàng trụ | Phép tính | Giá trị |
|---|---|---|---|
Thử lại: , , .
Cơ sở XOR với dãy (4 bit):
| Chèn | Nhị phân | Quá trình | basis[3..0] |
|---|---|---|---|
0001 |
bit 0 trống, đặt basis[0] = 1 |
0, 0, 0, 1 |
|
0110 |
bit 2 trống, đặt basis[2] = 6 |
0, 6, 0, 1 |
|
1100 |
bit 3 trống, đặt basis[3] = 12 |
12, 6, 0, 1 |
|
0110 |
bit 2: XOR với 6 còn 0, phụ thuộc | không đổi |
Hạng , nên có giá trị XOR khác nhau. Tham lam: (bit 3), thử nên bỏ, bit 1 trống, nên lấy. XOR lớn nhất là .
Cài đặt
Số thực (Gauss-Jordan, chọn trụ lớn nhất)
const double EPS = 1e-9;
// Giải hệ a * x = b, a là ma trận n x (m+1) (cột cuối là vế phải).
// Trả về 0 nếu vô nghiệm, 1 nếu nghiệm duy nhất, 2 nếu vô số nghiệm; ans nhận một nghiệm.
int gauss(vector<vector<double>> a, vector<double>& ans) {
int n = a.size(), m = a[0].size() - 1;
vector<int> where(m, -1); // where[c] = hàng chứa trụ của cột c
for (int col = 0, row = 0; col < m && row < n; col++) {
int sel = row; // chọn trụ có |giá trị| lớn nhất (partial pivoting)
for (int i = row; i < n; i++)
if (fabs(a[i][col]) > fabs(a[sel][col])) sel = i;
if (fabs(a[sel][col]) < EPS) continue; // cột này không có trụ: ẩn tự do
swap(a[sel], a[row]);
where[col] = row;
for (int i = 0; i < n; i++) // khử cột col ở mọi hàng khác (Gauss-Jordan)
if (i != row) {
double c = a[i][col] / a[row][col];
for (int j = col; j <= m; j++) a[i][j] -= a[row][j] * c;
}
row++;
}
ans.assign(m, 0); // ẩn tự do gán 0
for (int c = 0; c < m; c++)
if (where[c] != -1) ans[c] = a[where[c]][m] / a[where[c]][c];
for (int i = 0; i < n; i++) { // kiểm tra lại: phát hiện hàng 0 = khác 0
double s = 0;
for (int j = 0; j < m; j++) s += ans[j] * a[i][j];
if (fabs(s - a[i][m]) > 1e-6) return 0;
}
for (int c = 0; c < m; c++)
if (where[c] == -1) return 2;
return 1;
}
EPS = 1e-9
# Giải hệ a * x = b, a là ma trận n x (m+1) (cột cuối là vế phải).
# Trả về (0 vô nghiệm | 1 nghiệm duy nhất | 2 vô số nghiệm, một nghiệm)
def gauss(a):
a = [row[:] for row in a]
n, m = len(a), len(a[0]) - 1
where = [-1] * m # where[c] = hàng chứa trụ của cột c
row = 0
for col in range(m):
if row == n:
break
sel = max(range(row, n), key=lambda i: abs(a[i][col])) # trụ lớn nhất
if abs(a[sel][col]) < EPS:
continue # ẩn tự do
a[sel], a[row] = a[row], a[sel]
where[col] = row
for i in range(n): # khử cột col ở mọi hàng khác (Gauss-Jordan)
if i != row:
c = a[i][col] / a[row][col]
for j in range(col, m + 1):
a[i][j] -= a[row][j] * c
row += 1
ans = [0.0] * m # ẩn tự do gán 0
for c in range(m):
if where[c] != -1:
ans[c] = a[where[c]][m] / a[where[c]][c]
for i in range(n): # kiểm tra lại: phát hiện hàng 0 = khác 0
s = sum(ans[j] * a[i][j] for j in range(m))
if abs(s - a[i][m]) > 1e-6:
return 0, ans
return (2 if -1 in where else 1), ans
Modulo số nguyên tố: giải hệ và tính định thức
const long long MOD = 1000000007;
long long power(long long a, long long b) {
long long res = 1;
a %= MOD;
for (; b > 0; b >>= 1) {
if (b & 1) res = res * a % MOD;
a = a * a % MOD;
}
return res;
}
// Giải hệ theo modulo số nguyên tố MOD; a là n x (m+1), mọi phần tử trong [0, MOD).
// Trả về số ẩn tự do (>= 0), hoặc -1 nếu vô nghiệm; ans nhận một nghiệm (ẩn tự do = 0).
int gauss_mod(vector<vector<long long>> a, vector<long long>& ans) {
int n = a.size(), m = a[0].size() - 1, row = 0;
vector<int> where(m, -1);
for (int col = 0; col < m && row < n; col++) {
int sel = -1; // modulo p chỉ cần trụ khác 0, không cần lớn nhất
for (int i = row; i < n; i++)
if (a[i][col] != 0) { sel = i; break; }
if (sel == -1) continue;
swap(a[sel], a[row]);
where[col] = row;
long long inv = power(a[row][col], MOD - 2); // chia = nhân nghịch đảo
for (int j = col; j <= m; j++) a[row][j] = a[row][j] * inv % MOD;
for (int i = 0; i < n; i++)
if (i != row && a[i][col] != 0) {
long long c = a[i][col];
for (int j = col; j <= m; j++) a[i][j] = (a[i][j] - c * a[row][j] % MOD + MOD) % MOD;
}
row++;
}
for (int i = row; i < n; i++) // hàng toàn 0 bên trái nhưng vế phải khác 0
if (a[i][m] != 0) return -1;
ans.assign(m, 0);
for (int c = 0; c < m; c++)
if (where[c] != -1) ans[c] = a[where[c]][m];
return m - row;
}
// Định thức ma trận vuông theo modulo MOD: đưa về tam giác trên, đổi hàng thì đổi dấu.
long long det_mod(vector<vector<long long>> a) {
int n = a.size();
long long det = 1;
for (int col = 0; col < n; col++) {
int sel = -1;
for (int i = col; i < n; i++)
if (a[i][col] != 0) { sel = i; break; }
if (sel == -1) return 0;
if (sel != col) { swap(a[sel], a[col]); det = (MOD - det) % MOD; }
det = det * a[col][col] % MOD;
long long inv = power(a[col][col], MOD - 2);
for (int i = col + 1; i < n; i++) {
long long c = a[i][col] * inv % MOD;
for (int j = col; j < n; j++) a[i][j] = (a[i][j] - c * a[col][j] % MOD + MOD) % MOD;
}
}
return det;
}
MOD = 1000000007
# Giải hệ theo modulo số nguyên tố MOD; a là n x (m+1), phần tử trong [0, MOD).
# Trả về (số ẩn tự do hoặc -1 nếu vô nghiệm, một nghiệm với ẩn tự do = 0)
def gauss_mod(a):
a = [row[:] for row in a]
n, m = len(a), len(a[0]) - 1
where = [-1] * m
row = 0
for col in range(m):
if row == n:
break
sel = next((i for i in range(row, n) if a[i][col]), -1) # trụ khác 0
if sel == -1:
continue
a[sel], a[row] = a[row], a[sel]
where[col] = row
inv = pow(a[row][col], MOD - 2, MOD) # chia = nhân nghịch đảo
a[row] = [v * inv % MOD for v in a[row]]
for i in range(n):
if i != row and a[i][col]:
c = a[i][col]
a[i] = [(x - c * y) % MOD for x, y in zip(a[i], a[row])]
row += 1
if any(a[i][m] for i in range(row, n)): # hàng 0 = khác 0
return -1, None
ans = [0] * m
for c in range(m):
if where[c] != -1:
ans[c] = a[where[c]][m]
return m - row, ans
# Định thức ma trận vuông theo modulo MOD: đưa về tam giác trên, đổi hàng thì đổi dấu.
def det_mod(a):
a = [row[:] for row in a]
n = len(a)
det = 1
for col in range(n):
sel = next((i for i in range(col, n) if a[i][col]), -1)
if sel == -1:
return 0
if sel != col:
a[sel], a[col] = a[col], a[sel]
det = -det % MOD
det = det * a[col][col] % MOD
inv = pow(a[col][col], MOD - 2, MOD)
for i in range(col + 1, n):
c = a[i][col] * inv % MOD
if c:
a[i] = [(x - c * y) % MOD for x, y in zip(a[i], a[col])]
return det
: cơ sở XOR
Với hệ phương trình tổng quát trên , dùng đúng khung gauss_mod nhưng mỗi hàng là một bitset<N>, phép khử là a[i] ^= a[row]. Bản dưới là trường hợp hay gặp nhất: cơ sở của các số nguyên dưới .
// Cơ sở XOR (khử Gauss trên GF(2)): basis[b] là vector có bit cao nhất là b, hoặc 0.
struct XorBasis {
long long basis[60] = {};
int rank = 0;
// Thêm x; trả về false nếu x đã biểu diễn được bằng các vector cũ
bool insert(long long x) {
for (int b = 59; b >= 0; b--) {
if (!(x >> b & 1)) continue;
if (!basis[b]) { basis[b] = x; rank++; return true; }
x ^= basis[b]; // khử bit b, giống trừ hàng trụ
}
return false;
}
// XOR lớn nhất của một tập con: tham lam từ bit cao xuống
long long max_xor() {
long long r = 0;
for (int b = 59; b >= 0; b--)
if ((r ^ basis[b]) > r) r ^= basis[b];
return r;
}
// Số giá trị XOR khác nhau của các tập con là 2^rank
};
# Cơ sở XOR (khử Gauss trên GF(2)): basis[b] là vector có bit cao nhất là b, hoặc 0.
class XorBasis:
def __init__(self, bits=60):
self.basis = [0] * bits
self.rank = 0
# Thêm x; trả về False nếu x đã biểu diễn được bằng các vector cũ
def insert(self, x):
for b in range(len(self.basis) - 1, -1, -1):
if not (x >> b & 1):
continue
if not self.basis[b]:
self.basis[b] = x
self.rank += 1
return True
x ^= self.basis[b] # khử bit b, giống trừ hàng trụ
return False
# XOR lớn nhất của một tập con: tham lam từ bit cao xuống
def max_xor(self):
r = 0
for v in reversed(self.basis):
if r ^ v > r:
r ^= v
return r
Độ phức tạp
| Bài toán | Thời gian | Bộ nhớ |
|---|---|---|
| Giải hệ (số thực hoặc modulo ) | ||
| Định thức / nghịch đảo ma trận | ||
Hệ trên với bitset |
||
| Chèn một số vào cơ sở XOR bit |
Mỗi cột có trụ gây ra một lượt khử trên hàng, mỗi hàng phép tính, và có tối đa trụ. Bản modulo thêm một lần lũy thừa mỗi trụ, không đáng kể. Với , khoảng phép nhân: C++ chạy dưới một giây, Python thuần thì quá chậm (nên dùng phép toán trên cả hàng như zip ở trên, hoặc chỉ dùng cho cỡ đến ).
⚠️ Lỗi thường gặp
- Không chọn trụ lớn nhất trên số thực: chia cho trụ cỡ làm nổ sai số; luôn chọn lớn nhất và so với thay vì so với 0.
- Quên kiểm tra vô nghiệm: sau khi khử, các hàng không có trụ phải có vế phải bằng 0; bỏ qua bước này sẽ in "nghiệm" cho hệ vô nghiệm.
- Dùng sai
rowvàcol: khi một cột không có trụ, chỉ tăngcol, không tăngrow. Viếtfor (i = 0; i < n; i++)dùngicho cả hàng lẫn cột chỉ đúng khi ma trận khả nghịch. - Modulo âm trong C++:
(a - c * b) % MODcó thể âm; cộngMODtrước khi lấy dư. Vàc * bphải làlong long. - Quên đổi dấu định thức mỗi lần đổi chỗ hai hàng, hoặc chia cho trụ mà quên nhân trụ vào định thức.
- Cơ sở XOR với số 64 bit: dịch
1 << bvớib >= 31là trànint; dùng1LL << bhoặcx >> b & 1như trên. Bảngbasisphải đủ số bit của dữ liệu.
Biến thể / Mở rộng
- Ma trận nghịch đảo: khử Gauss-Jordan trên ma trận ghép ; khi bên trái thành thì bên phải là .
- Định lý Kirchhoff (ma trận cây): số cây khung của đồ thị bằng định thức của ma trận Laplace bỏ một hàng một cột, tính bằng
det_mod. - Xích Markov hấp thụ: kỳ vọng số bước và xác suất kết thúc là nghiệm của hệ tuyến tính; xem Chuỗi Markov và kỳ vọng qua hệ phương trình và DP xác suất & kỳ vọng.
- Khử trạng thái (GTH): khi hệ xác suất kém điều kiện, khử từng trạng thái chỉ bằng cộng, nhân, chia số không âm để giữ sai số tương đối nhỏ.
- Định thức của ma trận đa thức: tính giá trị tại các căn đơn vị (NTT), khử Gauss tại từng điểm, rồi nội suy ngược; xem FFT.
- Cơ sở XOR nâng cao: phần tử nhỏ thứ (đưa cơ sở về dạng rút gọn), cơ sở trên tiền tố có lưu chỉ số để trả lời truy vấn đoạn, cơ sở chu trình của đồ thị (XOR đường đi). Liên hệ Bitset Optimization.
Bài tập luyện
- XOR Tập Con Lớn Nhất (xorsubset): (Hard) Tìm XOR lớn nhất của một tập con số; dựng cơ sở XOR rồi tham lam từ bit cao.
- XOR cực đại tập con (xorbasis): (Very Hard) XOR lớn nhất của một tập con với giá trị tới ; cơ sở tuyến tính trên rồi tham lam từ bit cao.
- Hệ phương trình tuyến tính (linearsys): (Very Hard) Giải hệ theo modulo , báo vô nghiệm hoặc in một nghiệm bất kỳ; đúng bài
gauss_mod. - Đồ thị (icpc25mbe): (Very Hard) Đánh số cạnh để tối thiểu kỳ vọng tổng điểm của bước đi ngẫu nhiên; số lần qua mỗi đỉnh là nghiệm của hệ ẩn trên số thực.
- Xác suất dễ (icpc19nate): (Very Hard) Xác suất thắng trong trò tung đồng xu với hai xâu đích; hệ xích Markov trên automaton kém điều kiện, giải bằng khử trạng thái kiểu GTH.
- Ống dẫn quỹ đạo kín (icpc26mbg): (Master) Đếm có trọng số các nhật ký vận hành trên vòng; đáp án là hệ số của định thức một ma trận đa thức, tính bằng NTT và khử Gauss modulo tại từng căn đơn vị.
Bình luận