Wiki › Thuật toán › Toán học › Biến đổi Walsh-Hadamard (FWHT)

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.

huunguyen huunguyen Updated Tháng 11. 16, 2026 Đọc 13 phút 3 lượt xem

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 a,b độ dài n=2k, tìm

ck=∑i⊕j=kaibj

với ⊕ là XOR (hoặc AND, OR). Làm trực tiếp tốn O(n2)=O(4k); FWHT làm trong O(nlogn)=O(k·2k), nên với k=20 (giá trị tới khoảng 106) chỉ mất khoảng 2·107 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 x.

Ý tưởng / Trực giác

Trường hợp 1 bit. Với n=2, tích chập XOR của (a0,a1) và (b0,b1) là c0=a0b0+a1b1, c1=a0b1+a1b0. Đổi sang tổng và hiệu: (a0+a1)(b0+b1)=c0+c1 và (a0−a1)(b0−b1)=c0−c1. Vậy trong miền (u+v,u−v), tích chập thành phép nhân từng vị trí. Đây là ma trận Hadamard H=(111−1).

Trường hợp k bit. Áp dụng phép "tổng, hiệu" lần lượt theo từng bit (ma trận H⊗k), ta được

a^y=∑iai(−1)popcount(i&y).

Bổ đề (định lý tích chập). (a*b)^y=a^y·b^y. Chứng minh: hàm χy(i)=(−1)popcount(i&y) có tính nhân χy(i⊕j)=χy(i)χy(j), vì bit t của i⊕j là it+jt(mod2), nên số bit 1 chung với y cộng lại theo modulo 2. Do đó

(a*b)^y=∑i,jaibjχy(i⊕j)=(∑iaiχy(i))(∑jbjχy(j))=a^yb^y.

Biến đổi ngược. H·H=2I, nên H⊗k·H⊗k=nI: biến đổi ngược chính là biến đổi xuôi rồi chia cho n. Theo modulo số nguyên tố, chia là nhân nghịch đảo của n.

AND và OR. Với AND, dùng biến đổi "tổng trên tập cha" a^m=∑s⊇mas. Vì i&j chứa m khi và chỉ khi cả i và j đều chứa m, ta có (a*&b)^m=a^mb^m. Với OR, dùng "tổng trên tập con" a^m=∑s⊆mas (chính là SOS DP), vì i∣j⊆m khi và chỉ khi i⊆m và j⊆m. 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 (u,v) với u không có bit đang xét, v có bit đó:

Phép Xuôi Ngược
XOR (u,v)→(u+v, u−v) như xuôi, cuối cùng chia cho n
AND (u,v)→(u+v, v) (u,v)→(u−v, v)
OR (u,v)→(u, u+v) (u,v)→(u, v−u)

Lũy thừa tích chập. Tích chập XOR của a với chính nó K lần (K tới 1018) là biến đổi một lần, lũy thừa từng vị trí a^yK, rồi biến đổi ngược: không cần lặp K lần.

Ví dụ chạy tay

Một túi có các số: một số 0, hai số 1, ba số 3 (2 bit). Đếm số cặp có thứ tự (x,y) lấy từ túi (có hoàn lại) theo giá trị x⊕y. Mảng đếm a=[1,2,0,3] (chỉ số là giá trị), cần c=a*a.

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í: c^=[36,16,0,4]. Biến đổi lại: bit 0 cho [52,20,4,−4], bit 1 cho [56,16,48,24]; chia cho n=4:

x⊕y 0 1 2 3 Tổng
c 14 4 12 6 36=62
Kiểm tra 12+22+32 2·1·2 (cặp 0,1) 2·2·3 (cặp 1,3) 2·1·3 (cặp 0,3)

Cùng mảng đó, tích chập AND cho [11,16,0,9] và tích chập OR cho [1,8,0,27] (đã kiểm bằng vét cạn). Theo modulo 998244353, mảng sau biến đổi xuôi [6,−4,0,2] được lưu là [6,998244349,0,2].

Cài đặt

Tất cả làm theo modulo p=998244353; độ dài mảng phải là lũy thừa của 2 (đệm số 0 nếu cần).

C++
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;
}
Python
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 0,7 giây cho mỗi lần biến đổi với n=220 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 n=2k phần tử O(nlogn)=O(k2k) O(n), tại chỗ
Tích chập hai mảng 3 lần FWHT +O(n) O(n)
Lũy thừa tích chập bậc K 2 lần FWHT +O(nlogK) O(n)
Tích chập trực tiếp (để so sánh) O(n2) O(n)

Mỗi tầng len duyệt qua n/2 cặp (u,v), có log2n 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 n ở 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 n=2k với 2k lớn hơn giá trị lớn nhất (giá trị tới 1000 thì n=1024). Dùng n=max+1 làm vòng len bỏ sót phần tử. XOR, AND, OR của các số dưới 2k vẫn dưới 2k, nên không cần đệm thêm.
  • Quên chia cho n ở 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: u−v 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 a^yK, không thay K bằng Kmod(p−1) một cách mù quáng: nếu a^y≡0 thì 0K=0 với K≥1 nhưng 00=1.
  • 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ự: a*a đếm cặp có thứ tự và cả cặp (i,i); muốn cặp i<j thì trừ phần đường chéo rồi chia đôi.

Biến thể / Mở rộng

  • Cơ số 3 và nhóm (ℤm)k: thay ma trận H bằng ma trận Fourier cỡ m (với căn bậc m của đơn vị theo modulo p, cần m∣p−1), á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 {0,1}n: các hàm χT 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): cS=∑T⊆SaTbS⧵T (hai phần rời nhau), làm bằng OR-transform phân tầng theo số bit, O(k22k).
  • 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 GF(2) 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 n≤109 đố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 n.
  • 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 f, đếm số cặp đỉnh trên cây có XOR đường đi bằng f; XOR đường đi là du⊕dv nên đáp án là tích chập XOR của mảng đếm d 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 {0,1}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 x cho mọi x; đâ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 K≤1018 đống; biến đổi Walsh-Hadamard cơ số 3 trên (ℤ3)10 rồi lũy thừa từng vị trí.
Trang này có hữu ích không? Đăng nhập để trả lời

Bình luận

Không có bình luận tại thời điểm này.

gnatmake 12.2.0 a68g 3.1.2 nasm 2.16.1 as_x64 2.47 awk 1.3.4 gcc 16.2.0 dotnet 10.0.402 g++ 16.2.0 g++-themis 16.2.0 g++17 16.2.0 g++20 16.2.0 g++23 16.2.0 clang++ 22.1.8 dmd 2.113.0 dart 3.13.6 gforth 0.7.3 gfortran 15.3.0 go 1.27.3 groovyc 5.1.3 javac 26.0.2.1 node 26.12.1 julia 1.13.2 kotlinc 2.4.21 lean 4.35.0 sbcl 2.2.9 lua 5.5.1 nim 2.2.12 fpc 3.2.2 fpc-themis 3.2.2 perl 5.42.3 php 8.5.12 pike 8.0 swipl 9.0.4 pypy3 7.3.23 python3 3.15.1 racket 8.7 ruby 4.0.8 rustc 1.99.1 csc 5.3.0 ctoj-scratch 0.0.1 sed 4.9 swiftc 6.4.1 tclsh 8.6 bun 1.4.4 deno 2.9.8 v 0.5.2 zig 0.17.0