Biến đổi Walsh-Hadamard (FWHT)
Tính tích chập theo XOR, AND, OR của hai mảng độ dài 2^k trong O(k 2^k) bằng cách biến đổi sang miền mà tích chập thành phép nhân từng vị trí. Gồm chứng minh định lý tích chập, ví dụ chạy tay và cài đặt theo modulo.
Biến đổi Walsh-Hadamard nhanh (Fast Walsh-Hadamard Transform, FWHT) tính tích chập theo phép toán bit: cho hai mảng độ dài , tìm
với là XOR (hoặc AND, OR). Làm trực tiếp tốn ; FWHT làm trong , nên với (giá trị tới khoảng ) chỉ mất khoảng phép tính.
Ý tưởng giống hệt FFT: biến đổi hai mảng sang một "miền" mà ở đó tích chập trở thành nhân từng vị trí, nhân, rồi biến đổi ngược. Ứng dụng điển hình: phân phối XOR của tổng nhiều đại lượng độc lập (Nim ngẫu nhiên), đếm cặp có XOR (hoặc AND, OR) bằng một giá trị, đếm số cách chọn mỗi nhóm một phần tử để XOR bằng .
Ý tưởng / Trực giác
Trường hợp 1 bit. Với , tích chập XOR của và là , . Đổi sang tổng và hiệu: và . Vậy trong miền , tích chập thành phép nhân từng vị trí. Đây là ma trận Hadamard .
Trường hợp bit. Áp dụng phép "tổng, hiệu" lần lượt theo từng bit (ma trận ), ta được
Bổ đề (định lý tích chập). . Chứng minh: hàm có tính nhân , vì bit của là , nên số bit 1 chung với cộng lại theo modulo 2. Do đó
Biến đổi ngược. , nên : biến đổi ngược chính là biến đổi xuôi rồi chia cho . Theo modulo số nguyên tố, chia là nhân nghịch đảo của .
AND và OR. Với AND, dùng biến đổi "tổng trên tập cha" . Vì chứa khi và chỉ khi cả và đều chứa , ta có . Với OR, dùng "tổng trên tập con" (chính là SOS DP), vì khi và chỉ khi và . Biến đổi ngược là phép Möbius: cùng vòng lặp nhưng trừ thay vì cộng. Trên một cặp với không có bit đang xét, có bit đó:
| Phép | Xuôi | Ngược |
|---|---|---|
| XOR | như xuôi, cuối cùng chia cho | |
| AND | ||
| OR |
Lũy thừa tích chập. Tích chập XOR của với chính nó lần ( tới ) là biến đổi một lần, lũy thừa từng vị trí , rồi biến đổi ngược: không cần lặp lần.
Ví dụ chạy tay
Một túi có các số: một số , hai số , ba số (2 bit). Đếm số cặp có thứ tự lấy từ túi (có hoàn lại) theo giá trị . Mảng đếm (chỉ số là giá trị), cần .
FWHT xuôi, từng bit:
chỉ số: 0 1 2 3
a: 1 2 0 3
bit 0 (len=1): 1+2 1-2 0+3 0-3 = [ 3, -1, 3, -3]
\_____/ \_____/
bit 1 (len=2): 3+3 -1-3 3-3 -1+3 = [ 6, -4, 0, 2]
\___________/
Bình phương từng vị trí: . Biến đổi lại: bit 0 cho , bit 1 cho ; chia cho :
| 0 | 1 | 2 | 3 | Tổng | |
|---|---|---|---|---|---|
| Kiểm tra | (cặp ) | (cặp ) | (cặp ) |
Cùng mảng đó, tích chập AND cho và tích chập OR cho (đã kiểm bằng vét cạn). Theo modulo , mảng sau biến đổi xuôi được lưu là .
Cài đặt
Tất cả làm theo modulo ; độ dài mảng phải là lũy thừa của 2 (đệm số 0 nếu cần).
const long long MOD = 998244353;
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;
}
// Biến đổi Walsh-Hadamard cho XOR; a.size() phải là lũy thừa của 2.
// invert = true: biến đổi ngược (biến đổi xuôi rồi chia cho n).
void fwht_xor(vector<long long>& a, bool invert) {
int n = a.size();
for (int len = 1; len < n; len <<= 1)
for (int i = 0; i < n; i += 2 * len)
for (int j = i; j < i + len; j++) {
long long u = a[j], v = a[j + len];
a[j] = (u + v) % MOD; // (u, v) -> (u + v, u - v)
a[j + len] = (u - v + MOD) % MOD;
}
if (invert) {
long long inv_n = power(n, MOD - 2);
for (auto& x : a) x = x * inv_n % MOD;
}
}
// AND: a[mask] -> tổng a[sup] trên mọi sup chứa mask (zeta theo tập cha); ngược là Möbius.
void fwht_and(vector<long long>& a, bool invert) {
int n = a.size();
for (int len = 1; len < n; len <<= 1)
for (int i = 0; i < n; i += 2 * len)
for (int j = i; j < i + len; j++) // j không có bit len, j + len có
a[j] = invert ? (a[j] - a[j + len] + MOD) % MOD : (a[j] + a[j + len]) % MOD;
}
// OR: a[mask] -> tổng a[sub] trên mọi sub là tập con của mask (SOS); ngược là Möbius.
void fwht_or(vector<long long>& a, bool invert) {
int n = a.size();
for (int len = 1; len < n; len <<= 1)
for (int i = 0; i < n; i += 2 * len)
for (int j = i; j < i + len; j++)
a[j + len] = invert ? (a[j + len] - a[j] + MOD) % MOD : (a[j + len] + a[j]) % MOD;
}
// c[k] = tổng a[i] * b[j] trên mọi (i, j) với i op j = k; op là 'x' (XOR), '&' hoặc '|'.
vector<long long> convolve(vector<long long> a, vector<long long> b, char op) {
auto tf = op == 'x' ? fwht_xor : op == '&' ? fwht_and : fwht_or;
tf(a, false);
tf(b, false);
for (size_t i = 0; i < a.size(); i++) a[i] = a[i] * b[i] % MOD; // nhân từng vị trí
tf(a, true);
return a;
}
MOD = 998244353
# Biến đổi Walsh-Hadamard cho XOR; len(a) phải là lũy thừa của 2.
# invert = True: biến đổi ngược (biến đổi xuôi rồi chia cho n).
def fwht_xor(a, invert):
n = len(a)
h = 1
while h < n:
for i in range(0, n, 2 * h):
for j in range(i, i + h):
u, v = a[j], a[j + h]
a[j] = (u + v) % MOD # (u, v) -> (u + v, u - v)
a[j + h] = (u - v) % MOD
h *= 2
if invert:
inv_n = pow(n, MOD - 2, MOD)
for i in range(n):
a[i] = a[i] * inv_n % MOD
# AND: a[mask] -> tổng a[sup] trên mọi sup chứa mask (zeta theo tập cha); ngược là Möbius.
def fwht_and(a, invert):
n = len(a)
sign = -1 if invert else 1
h = 1
while h < n:
for i in range(0, n, 2 * h):
for j in range(i, i + h): # j không có bit h, j + h có
a[j] = (a[j] + sign * a[j + h]) % MOD
h *= 2
# OR: a[mask] -> tổng a[sub] trên mọi sub là tập con của mask (SOS); ngược là Möbius.
def fwht_or(a, invert):
n = len(a)
sign = -1 if invert else 1
h = 1
while h < n:
for i in range(0, n, 2 * h):
for j in range(i, i + h):
a[j + h] = (a[j + h] + sign * a[j]) % MOD
h *= 2
# c[k] = tổng a[i] * b[j] trên mọi (i, j) với i op j = k; op là "x" (XOR), "&" hoặc "|".
def convolve(a, b, op):
tf = {"x": fwht_xor, "&": fwht_and, "|": fwht_or}[op]
a, b = a[:], b[:]
tf(a, False)
tf(b, False)
a = [x * y % MOD for x, y in zip(a, b)] # nhân từng vị trí
tf(a, True)
return a
Bản Python thuần với vòng lặp từng phần tử mất khoảng giây cho mỗi lần biến đổi với trên máy thử (một tích chập cần 3 lần); khi cần nhanh hơn, xử lý cả nửa mảng một lúc bằng cắt lát (a[i:i+h], a[i+h:i+2h]) và zip, hoặc đóng gói nhiều giá trị vào một số nguyên lớn.
Độ phức tạp
| Thao tác | Thời gian | Bộ nhớ |
|---|---|---|
| Một lần FWHT (XOR, AND hay OR) trên phần tử | , tại chỗ | |
| Tích chập hai mảng | lần FWHT | |
| Lũy thừa tích chập bậc | lần FWHT | |
| Tích chập trực tiếp (để so sánh) |
Mỗi tầng len duyệt qua cặp , có tầng. Khác với FFT, không có số phức hay căn đơn vị, chỉ có cộng và trừ, nên FWHT rất nhanh và chính xác tuyệt đối trên số nguyên. Khi không cần modulo và giá trị nhỏ, có thể dùng long long thuần rồi chia cho ở cuối (kết quả luôn chia hết).
⚠️ Lỗi thường gặp
- Độ dài không phải lũy thừa của 2: phải đệm số 0 tới với lớn hơn giá trị lớn nhất (giá trị tới thì ). Dùng làm vòng
lenbỏ sót phần tử. XOR, AND, OR của các số dưới vẫn dưới , nên không cần đệm thêm. - Quên chia cho ở biến đổi ngược của XOR (hoặc chia ở cả xuôi lẫn ngược). AND và OR thì không chia: biến đổi ngược của chúng là phép trừ.
- Modulo âm: trong C++ có thể âm, cần
+ MOD; trong Python%đã cho số không âm. - Lấy lũy thừa với số mũ rút gọn: khi tính , không thay bằng một cách mù quáng: nếu thì với nhưng .
- Dùng nhầm biến đổi: tích chập AND cần tổng trên tập cha, OR cần tổng trên tập con; đổi chỗ hai hướng cho kết quả sai nhưng vẫn "trông hợp lý" trên ví dụ đối xứng.
- Đếm cặp có thứ tự và không thứ tự: đếm cặp có thứ tự và cả cặp ; muốn cặp thì trừ phần đường chéo rồi chia đôi.
Biến thể / Mở rộng
- Cơ số 3 và nhóm : thay ma trận bằng ma trận Fourier cỡ (với căn bậc của đơn vị theo modulo , cần ), áp dụng theo từng chữ số. Dùng cho Nim của Moore (bốc từ tối đa 2 đống), nơi điều kiện thua là "mỗi bit có số đống chia hết cho 3".
- Bước đi ngẫu nhiên trên : các hàm là véctơ riêng của ma trận chuyển, nên thời gian chạm có công thức đóng qua biến đổi Walsh-Hadamard; xem Chuỗi Markov và kỳ vọng qua hệ phương trình.
- Tích chập tập con (subset convolution): (hai phần rời nhau), làm bằng OR-transform phân tầng theo số bit, .
- Liên hệ: SOS DP chính là biến đổi OR, FFT là bản tích chập theo phép cộng, Khử Gauss trên trả lời "XOR nào đạt được" (không đếm số cách).
Bài tập luyện
- Trò chơi Nim ngẫu nhiên (nimprob): (Very Hard) Xác suất người đi trước thắng khi đống có kích thước ngẫu nhiên; phân phối XOR là lũy thừa tích chập XOR bậc .
- Tất Cả XOR Mảng Con (xorsubarr): (Very Hard) Liệt kê mọi giá trị XOR của mảng con; XOR hai tiền tố, nên cần tích chập XOR của mảng đếm tiền tố với chính nó.
- Đếm đường đi XOR (thpn26_xorpathcnt): (Very Hard) Với mỗi , đếm số cặp đỉnh trên cây có XOR đường đi bằng ; XOR đường đi là nên đáp án là tích chập XOR của mảng đếm với chính nó.
- Câu đố tủ khóa II (icpc26mnk): (Expert) Kỳ vọng số thao tác ngẫu nhiên tới khi mọi tủ đóng; bước đi ngẫu nhiên trên được chéo hóa bằng các đặc trưng Walsh-Hadamard, rút về một bài đếm cái túi.
- Cây khung xor (xorspan): (Expert) Chọn cây khung tối ưu theo XOR trọng số trên đồ thị có tối đa 42 chu trình rời đỉnh; mỗi chu trình bỏ đúng một cạnh, nên số cách đạt mỗi giá trị XOR là tích chập XOR các mảng đếm của từng chu trình.
- Đếm cặp có AND bằng x (sosboss): (Expert) Đếm số cặp có AND đúng bằng cho mọi ; đây là tích chập AND của mảng tần suất với chính nó: tổng siêu tập, bình phương từng vị trí, rồi biến đổi ngược.
- Nim (icpc23mbi): (Expert) Đếm cấu hình thua của Nim bốc từ tối đa 2 đống với đống; biến đổi Walsh-Hadamard cơ số 3 trên rồi lũy thừa từng vị trí.
Bình luận