Phần kiến thức nền tảng

Tổng缀 các chiều cao

Đa thức tích chập

Đầu tiên, đây là một mẫu mã:

P4717

FWT được sử dụng để giải quyết các tích chập như sau:

trong đó \(\\oplus\\) là một trong ba phép toán bit.

Độ phức tạp thời gian của FWT là \(O(n2^n)\), nếu coi \(2^n\) là \(n\), thì độ phức tạp thời gian tương tự như FFT, NTT.

Tích chập AND

Định nghĩa \(A'(x)\) là \(\sum_{x\in y}A(y)\), đây là một biến đổi FWT, rõ ràng biến đổi này có thể được thực hiện trực tiếp bằng tổng缀 các chiều cao.

void bienDoiFMT(int *mangGoc, int *mangKetQua, int kichThuoc) {
    for(int i = 0; i < kichThuoc; i++) mangKetQua[i] = mangGoc[i];
    for(int i = 0; i < n; i++)
        for(int j = kichThuoc - 1; j >= 0; j--)
            if(j & (1 << i)) mangKetQua[j^(1 << i)] += mangKetQua[j];
}

Sau đó, ta sẽ phát hiện một công thức đáng ngạc nhiên:

Bằng chứng rất đơn giản, xem xét biểu thức sau thực chất là:

Sau đó sẽ thấy \(x\in (y_1\cap y_2)\), vì vậy cách tính này rõ ràng bằng với vế phải.

Xem xét cách chuyển từ \(F'(x)\) thành \(F(x)\).

Thực chất chỉ cần trừ lại, đổi dấu cộng thành trừ là được.

void bienDoiNghichFMT(int *mangGoc, int *mangKetQua, int kichThuoc) {
    for(int i = 0; i < kichThuoc; i++) mangKetQua[i] = mangGoc[i];
    for(int i = 0; i < n; i++)
        for(int j = kichThuoc - 1; j >= 0; j--)
            if(j & (1 << i)) mangKetQua[j^(1 << i)] -= mangKetQua[j];
}

Sau đó bạn sẽ thấy, sự khác biệt giữa hai hàm này chỉ là một dấu, có thể đưa một tham số \(T\) vào để điều khiển.

Cách viết tích chập tương tự như FFT:

void tinhTichChapAnd(int *mangA, int *mangB, int *mangKetQua, int kichThuoc) {
    bienDoiFMT(mangA, mangA, kichThuoc);
    bienDoiFMT(mangB, mangB, kichThuoc);
    for(int i = 0; i < kichThuoc; i++) mangKetQua[i] = mangA[i] * mangB[i];
    bienDoiNghichFMT(mangKetQua, mangKetQua, kichThuoc);
}

Vậy là xong tích chập AND.

Tích chập OR

Tương tự như trên, có thể thấy bản chất chỉ cần thay đổi thứ tự liệt kê là được.

Về cách viết

Cách viết FWT có thể giống với FFT để trông đẹp hơn.

// Tích chập AND
void chuyenDoiAnd(int *mang, int nhan) {
    for(int doDai = 1; doDai < 1 << n; doDai <<= 1)
        for(int viTri = 0; viTri < 1 << n; viTri += (doDai << 1))
            for(int chiSo = 0; chiSo < doDai; chiSo++)
                mang[viTri + chiSo] = mang[viTri + chiSo] + mang[viTri + chiSo + doDai] * nhan;
}
// Tích chập OR
void chuyenDoiOr(int *mang, int nhan) {
    for(int doDai = 1; doDai < 1 << n; doDai <<= 1)
        for(int viTri = 0; viTri < 1 << n; viTri += (doDai << 1))
            for(int chiSo = 0; chiSo < doDai; chiSo++)
                mang[viTri + chiSo + doDai] = mang[viTri + chiSo] * nhan + mang[viTri + chiSo + doDai];
}

Có thể thấy bản chất của \(len\) là liệt kê từng bit, \(l\) liệt kê các bit trước đó, \(k\) là các bit sau, và sau đó tương tự như cách viết trên.

Lợi ích của cách viết này là, dù là phép toán nào, chỉ cần thỏa mãn với hai số, có thể viết trực tiếp vào bên trong.

Tích chập XOR

Cuối cùng được trình bày vì thực sự quá khó.

Xây dựng thần thánh: \(F'(x)=\sum_{i*x=0}F(i)-\sum_{i*x=1}F(i)\).

Gọi \(p(x)\) là số bit có giá trị 1 trong biểu diễn nhị phân của \(x\), thì phép toán \(*\) ở trên biểu thị \(p(i\& x)\mod 2\).

Có thể thấy \((i*x)\ xor\ (i*y)=i*(x\ xor\ y)\).

Bằng chứng rất đơn giản, xét từng bit, nếu bit của \(i\) là 0, thì cả hai vế đều là 0, nếu \(i\) là 1, thì nếu \(x,y\) có 1 sẽ tạo ra giá trị 1, lại có modulo 2, nên hai vế bằng nhau.

Xem xét cách thực hiện, với hai số chỉ khác nhau một bit, thực chất là số trước cộng với số sau, số sau trừ đi số trước.

Biến đổi ngược cũng rất đơn giản, chỉ cần khôi phục lại là được.

void chuyenDoiXor(int *mang, int nhan) {
    for(int doDai = 1; doDai < 1 << n; doDai <<= 1)
        for(int viTri = 0; viTri < 1 << n; viTri += (doDai << 1))
            for(int chiSo = 0; chiSo < doDai; chiSo++) {
                int giaTri1 = mang[viTri + chiSo];
                int giaTri2 = mang[viTri + chiSo + doDai];
                mang[viTri + chiSo] = giaTri1 + giaTri2;
                mang[viTri + chiSo + doDai] = giaTri1 - giaTri2;
                if(nhan == -1) {
                    mang[viTri + chiSo] = mang[viTri + chiSo] / 2;
                    mang[viTri + chiSo + doDai] = mang[viTri + chiSo + doDai] / 2;
                }
            }
}

Cuối cùng, ta có mã nguồn cho bài P4717

Ghi chép giải bài tập

P6097

Cho hai dãy độ dài \(2^n\) là \(A, B\), tính kết quả tích con tập của chúng.

\[c_k=\sum_{\substack{{i \& j=0}\\{i~\mid~ j=k}}} a_i b_j \]

\(n\le 20\).

Đây là một bài mẫu.

Xem xét điều kiện \(i \& j=0\) hơi phức tạp, nếu không có điều kiện này có thể dùng tích chập OR trực tiếp.

Gọi \(p(x)\) là số bit có giá trị 1 trong biểu diễn nhị phân của \(x\), thì có thể thấy \(p(i)+p(j)\ge p(i|j)\), chỉ khi \(p(i)+p(j)=p(i|j)\) thì \(i\& j=0\).

Khi đó có một ý tưởng là thêm một chiều hạn chế, giới hạn số bit, với mỗi tích chập OR sau đó thực hiện một tích chập đa thức.

Tức là

Sau đó khôi phục lại từng bit, độ phức tạp thời gian \(O(n^22^n)\) có thể qua được.

CF662C \*2600

Có một bảng với \(n\) hàng \(m\) cột, mỗi phần tử là \(0/1\), mỗi lần thao tác có thể chọn một hàng hoặc một cột, lật ngược các giá trị \(0/1\). Hỏi sau một số lần thao tác, bảng có ít số \(1\) nhất là bao nhiêu.

\(n\le 20,m\le 10^5\).

\(n\) nhỏ như vậy, rõ ràng nên nén mỗi cột về trạng thái, giả sử kết quả nén là \(b_i\).

Liệt kê thao tác trên hàng hiện tại \(x\), gọi \(g(x)\) là số lượng \(1\) nhỏ nhất có thể đạt được bằng cách lật ngược.

Gọi \(k_i=b_i\ xor\ x\), \(c_i\) là số lần \(b_i\) xuất hiện.

Rõ ràng là tích chập XOR, chỉ cần tính tích chập là được.

P4221

Bài hơi dài, tự xem nhé

Đầu tiên, để xác định một tập điểm có hợp lệ hay không có thể dùng暴力, chỉ cần kiểm tra không liên thông hoặc tồn tại điểm bậc lẻ là được, phần này có thể \(O(n2^n)\) trực tiếp.

Xem xét đã chọn bao nhiêu điểm, gọi \(f_{i,j}\) là tích của các điểm đã chọn \(i\) điểm, tập hợp là \(j\), đây rõ ràng là một tích con tập, liệt kê số điểm đã chọn ở vòng trước, nhân với kết quả xử lý sẵn ở trên.

Sau mỗi vòng lại chia cho tổng cả tập hợp, tức là vế dưới của công thức.

Làm như vậy \(n\) vòng là xong, độ phức tạp thời gian \(O(n^22^n)\).

P8292

Có \(n\) số \(a_i\), \(Q\) lần truy vấn, mỗi lần truy vấn cho \(k\) số nguyên tố, có thể chọn một số trong \(n\) số sao cho \(k\) số nguyên tố đều chia hết cho tích của các số đã chọn, tìm số cách modulo \(998244353\).

\(n\le 10^6,\sum k\le 18000,a_i\le 2000\).

Phát hiện \(a_i\le 2000\), dễ nghĩ đến phân tích căn bậc hai, có thể thấy các số nguyên tố \(\le \sqrt{2000}\) chỉ có 14 cái, có thể nén trạng thái.

Đầu tiên không xét các số \(> \sqrt{2000}\), có thể thấy bản chất đây là một tích chập OR, đặt \(f(x)\) là số cách chọn các số có ước số là tập hợp \(x\), kết quả tương đương với việc nhân các mảng \(f\) của \(n\) số lại với nhau.

Cách nhân nhanh? FWT tất cả các mảng, có thể thấy bản chất là một mảng các số khác \(1\), chứa \(a_i\) thì là \(2\), nên có thể cộng tất cả lại, sau khi FWT tính lũy thừa của \(2\).

Kết quả cuối cùng tương đương với IFWT rồi tính tổng hậu tố.

Sau đó xem xét các ước số \(> \sqrt{2000}\) làm thế nào, xem xét chia nhóm, mỗi số chia vào nhóm các ước số \(> \sqrt{2000}\) của nó, cuối cùng tương đương với việc nhân các nhóm lại, nếu một nhóm được chọn thì tương đương với loại bỏ phương án không chọn cái nào, tức là trừ đi một.

Độ phức tạp thời gian \(O(2^{14}\sum {c_i})\), chạy qua được dữ liệu thử nghiệm.

Lưu ý cần đặc biệt xử lý \(1849\), vì không có ước số nào \(<43\) có thể loại bỏ nó.