Người viết:
Reviewer:
Ở phần trước, chúng ta đã được tìm hiểu về DP Sum over Subsets, các biến thể cũng như một số bài tập minh họa. Trong phần tiếp theo, ta sẽ đào sâu hơn vào các dạng bài yêu cầu biến đổi khéo léo hơn để có thể áp dụng DP SoS qua ba phép nhân trên hàm số và tập hợp cũng như một số bài tập khác.
Tương tự phần trước, các kí hiệu của phép toán trên tập hợp sẽ được áp dụng cho cả ngôn ngữ bitmask.
Cho hai hàm với là ký hiệu tập các tập con của , ta định nghĩa phép gộp tập hợp cho ra hàm thỏa:
Trước tiên, ta định nghĩa hàm như sau:
Ở phần trước, ta đã biết cách khôi phục hàm từ hàm bằng DP SoS ngược hoặc Bao hàm loại trừ. Nhiệm vụ của chúng ta bây giờ là tính . Dễ thấy, điều kiện cũng tương đương với và , từ đó, ta biến đổi công thức tính:
Chúng ta lại trở về với bài toán Sum over Subsets trên hàm . Như vậy, ta đã giải quyết được bài toán trong .
Bằng ý tưởng tương tự, ta có thể giải quyết phép nhân như sau:
Định nghĩa hàm :
Cuối cùng, ta lại sử dụng DP SoS ngược để khôi phục từ . Độ phức tạp của thuật toán này cũng là .
Ở phần này, mình chỉ cài đặt OR Convolution, AND Convolution được thực hiện tương tự.
vector<int> sos (const vector<int> &f, int n, bool reversed = 0) {
vector<int> dp = f;
if (reversed) {
for (int k = n - 1; k >= 0; k--)
for (int mask = 0; mask < (1 << n); mask++)
if (mask & (1 << k)) dp[mask] -= dp[mask ^ (1 << k)];
}
else {
for (int k = 0; k < n; k++)
for (int mask = 0; mask < (1 << n); mask++)
if (mask & (1 << k)) dp[mask] += dp[mask ^ (1 << k)];
}
return dp;
}
vector<int> orConvolution (const vector<int> &f, const vector<int> &g, int n) {
vector<int> hhat(1 << n), fhat = sos(f, n), ghat = sos(g, n);
for (int mask = 0; mask < (1 << n); mask++)
hhat[mask] = fhat[mask] * ghat[mask];
return sos(hhat, n, 1);
}
Giả sử, ta cần thực hiện phép nhân nêu trên với ba hàm, tức là tính . Ta sẽ không thực hiện riêng từng phép nhân mà thực hiện DP SoS trên từng hàm, tính cho cả ba hàm rồi DP SoS ngược. Lúc này, công thức định nghĩa hàm là:
Ý tưởng tương tự cũng được áp dụng cho phép nhân hàm.
Tuy không giảm được độ phức tạp nhưng cách làm này tiết kiệm được một số bước và giảm hằng số của độ phức tạp một cách đáng kể.
Cho hai hàm với là ký hiệu tập các tập con của , ta định nghĩa phép nhân tập con cho ra hàm thỏa:
Ta biến đổi công thức định nghĩa như sau:
Với , ta có thể biến đổi điều kiện thành , vì nếu có phần giao thì . Do đó, ta cần thêm một chiều để kiểm soát kích thước của các tập con. Ta định nghĩa lại hàm thành hàm là:
Khi đó, mục tiêu của chúng ta là tính với mọi tập . Và để làm điều này, ta lại sử dụng ý tưởng tương tự phép nhân gộp tập hợp, định nghĩa hàm :
Để tính , ta cần tính hai hàm khác:
Sau đó, ta có thể tính bằng công thức:
Ta lại sử dụng DP SoS ngược để khôi phục từng hàm từ để đưa ra đáp án cuối cùng. Như vậy, thuật toán có độ phức tạp .
Trước tiên, ta cần tính các hàm và , việc tính toán được thực hiện tương tự DP SoS truyền thống: Gọi và lần lượt là hàm DP SoS trên hàm . Ở đây, ta chỉ lưu ý trường hợp cơ sở sẽ có một chút thay đổi:
Sau khi đã có hàm , ta thực hiện các bước còn lại như mô tả ở trên.
vector<int> sos (const vector<int> &f, int n, bool reversed = 0) {
vector<int> dp = f;
if (reversed) {
for (int k = n - 1; k >= 0; k--)
for (int mask = 0; mask < (1 << n); mask++)
if (mask & (1 << k)) dp[mask] -= dp[mask ^ (1 << k)];
}
else {
for (int k = 0; k < n; k++)
for (int mask = 0; mask < (1 << n); mask++)
if (mask & (1 << k)) dp[mask] += dp[mask ^ (1 << k)];
}
return dp;
}
vector<int> subsetConvolution (const vector<int> &f, const vector<int> &g, int n) {
vector<vector<int>> fhat(n + 1, vector<int>(1 << n)), ghat(n + 1, vector<int>(1 << n));
for (int mask = 0; mask < (1 << n); mask++) {
fhat[__builtin_popcount(mask)][mask] = f[mask];
ghat[__builtin_popcount(mask)][mask] = g[mask];
}
for (int i = 0; i <= n; i++)
fhat[i] = sos(fhat[i], n), ghat[i] = sos(ghat[i], n);
vector<vector<int>> hhat(n + 1, vector<int>(1 << n));
for (int i = 0; i <= n; i++)
for (int mask = 0; mask < (1 << n); mask++)
for (int j = 0; j <= i; j++)
hhat[i][mask] += fhat[j][mask] * ghat[i - j][mask];
for (int i = 0; i <= n; i++)
hhat[i] = sos(hhat[i], n, 1);
vector<int> h(1 << n);
for (int mask = 0; mask < (1 << n); mask++)
h[mask] = hhat[__builtin_popcount(mask)][mask];
return h;
}
Để kiểm tra code, bạn đọc có thể tìm bài Subset Convolution ở phần Phụ lục.
Với phép tính cuối cùng cũng như phép tính phức tạp nhất chính là phép hiệu đối xứng. Trước khi nghiên cứu đến phần này, bạn đọc cần biết trước về Fast Fourier Transform (FFT) và sơ lược về Fast Walsh-Hadamard Transform (FWHT).
Cho hai hàm với là ký hiệu tập các tập con của , ta định nghĩa phép nhân tập con cho ra hàm thỏa:
Phép hiệu đối xứng được định nghĩa tương tự phép XOR trên bitmask:
với (Iversion bracket) được định nghĩa là:
Để xử lý phép hiệu đối xứng một cách hiệu quả, ta cần lấy cảm hứng từ một thuật toán khác: Phép nhân đa thức bằng FFT. Nhìn chung, để nhân đa thức trong , ta cần thực hiện ba bước là biến đổi hàm bằng cách thế căn đơn vị thứ vào (Discrete Fourier Transform), nhân hệ số, rồi khôi phục lại tích của hai đa thức (Inversed Discrete Fourier Transform).
Với phép hiệu đối xứng, ta cũng sử dụng mô hình tương tự, nhưng thay vì sử dụng Discrete Fourier Transform (DFT), ta dùng Walsh-Hadamard Transform (WHT). Ta sẽ cùng tìm hiểu Walsh-Hadamard Transform và xây dựng một thuật toán Fast Walsh-Hadamard Transform dựa trên DP SoS.
Với WHT, ta chỉ xét các đa thức bậc .
Sự khác biệt giữa DFT và WHT là khi nhân hai số hạng và với nhau, DFT sẽ cho ra , còn đối với WHT, ta mong muốn sẽ cho ra . Rõ ràng, WHT đang phá đi tính chất tự nhiên của phép nhân và lũy thừa.
Để giải quyết điều này, ta tách ra thành hàm thừa số, với số mũ của từng thừa số ứng với trạng thái bật/tắt của bit tương ứng trong biểu diễn nhị phân của (giả sử cần xét bit đầu tiên). Nói cách khác, mỗi số hạng bây giờ sẽ có dạng (với là trạng thái của bit thứ , là hệ số của số hạng). Từ đây, ta có thể thấy rằng WHT về bản chất là FFT trên đa thức chiều bậc .
Với mỗi chiều của đa thức sau khi biến đổi, ta cần tính điểm phân biệt (tương tự FFT), vậy với cả đa thức, ta cần tính điểm.
Trở lại với vấn đề nêu trên, lúc này, khi số mũ chỉ còn là một bit, ta có thể dễ dàng biến đổi thành . Tức là ta vẫn có thể nhân đa thức bình thường, nhưng hệ số của các số hạng và phải được gộp lại thành một. Nói cách khác, ta cần chọn hai điểm phân biệt để tính có thỏa:
Dễ thấy, hai giá trị và thỏa mãn điều kiện này.
Như vậy, với Walsh-Hadamard Transform, ta được cho một đa thức chiều bậc có dạng . Ta cần tính giá trị đa thức tại điểm có dạng .
Để ý rằng mỗi điểm cần tính gồm tham số, mỗi tham số có cách chọn. Vì thế, ta có thể biểu diễn một bộ tham số dưới dạng một tập con của sao cho tham số thứ của tập biểu diễn là .
Từ những phân tích trên, ta định nghĩa WHT lại trên ngôn ngữ của hàm số và tập hợp. Cho hàm với là ký hiệu tập các tập con của , ta định nghĩa phép biển đổi Walsh-Hadamard của hàm là hàm sao cho:
Để tính , ta xử lý từng bit của hàm. Xét hàm chiều , ta có thể gom các số hạng của nó thành hai nhóm:
Tương tự, để tính , ta lại nhóm chúng thành hai nhóm theo số mũ của . Ta sẽ có nhóm là:
Như vậy, ý tưởng là tại tầng đệ quy thứ , ta nhóm các số hạng theo hậu tố chung độ dài rồi đem phần hậu tố này ra đặt làm nhân tử chung. Ta có nhóm và ở mỗi nhóm ta cần tính giá trị hàm tại điểm (do chỉ còn chưa được đặt làm nhân tử chung).
Ta định nghĩa là đa thức gồm các số hạng có hậu tố chung là sau khi đã bỏ phần hậu tố chung này đi.
Đến đây, ta có thể lấy ý tưởng chia một bitmask ra làm hai nửa để đặt trạng thái giống như DP SoS để áp dụng vào FWHT. Cụ thể, ta có thể biểu diễn trạng thái bằng cặp với ý nghĩa:
Ví dụ, cặp biểu diễn nhóm sau khi được thế lần lượt cho .
Như vậy, ta gọi là giá trị hàm theo định nghĩa như trên. Cụ thể hơn, giả sử bitmask có dạng , ta có:
Ta có trường hợp cơ sở là (phần nhân tử chung có bit và hàm không có bit nào).
Để tính , ta lại xét trường hợp:
Cuối cùng, ta có (phần nhân tử chung không có bit nào và hàm có bit).
Để rút gọn công thức hơn, ta đặt và , ta có công thức Quy hoạch động:
Như vậy, ta đã có thuật toán biến đổi Walsh-Hadamard trong
Sau khi đã có hàm
Vấn đề cuối cùng chưa được giải quyết là làm cách nào để khôi phục
Để giải quyết bài toán này, ta cần quay về cách giải thích FWHT nguyên thủy là phép nhân ma trận. Quá trình mà ta vừa thực hiện ở phần trên tương đương với việc biến hàm
với
Để khôi phục
Như vậy, để khôi phục
Đối với FWHT, ta không thể cài đặt theo cách tối ưu bộ nhớ của DP SoS được vì các giá trị của dòng hiện tại và dòng trước sẽ bị tính toán lẫn lộn. Do đó, cách xử lý đơn giản nhất là duy trì bảng QHĐ hai dòng rồi trả về dòng
vector<int> fwht (const vector<int> &f, int n, bool inversed = 0) {
vector<vector<int>> dp(2, vector<int>(1 << n));
dp[0] = f;
int sz = 1 << n;
for (int k = 1; k <= n; k++) {
int t = k & 1;
for (int mask = 0; mask < sz; mask++) {
int u = dp[t ^ 1][mask ^ (1 << (k - 1))], v = dp[t ^ 1][mask];
if (mask & (1 << (k - 1))) dp[t][mask] = u - v;
else dp[t][mask] = u + v;
}
}
if (inversed)
for (int mask = 0; mask < sz; mask++) dp[n & 1][mask] /= sz;
return dp[n & 1];
}
vector<int> xorConvolution (const vector<int> &f, const vector<int> &g, int n) {
int sz = 1 << n;
vector<int> hhat(sz), fhat = fwht(f, n), ghat = fwht(g, n);
for (int mask = 0; mask < sz; mask++)
hhat[mask] = fhat[mask] * ghat[mask];
return fwht(hhat, n, 1);
}
Để bỏ bớt một chiều trong bộ nhớ bảng QHĐ, ở mỗi vòng, ta bắt cặp các mask có dạng
vector<int> fwht (const vector<int> &f, int n, bool inversed = 0) {
vector<int> dp = f;
int sz = 1 << n;
for (int k = 0; k < n; k++) {
for (int mask = 0; mask < sz; mask++) {
if (!(mask & (1 << k))) continue;
int u = dp[mask ^ (1 << k)], v = dp[mask];
dp[mask ^ (1 << k)] = u + v, dp[mask] = u - v;
}
}
if (inversed)
for (int mask = 0; mask < sz; mask++) dp[mask] /= sz;
return dp;
}
vector<int> xorConvolution (const vector<int> &f, const vector<int> &g, int n) {
int sz = 1 << n;
vector<int> hhat(sz), fhat = fwht(f, n), ghat = fwht(g, n);
for (int mask = 0; mask < sz; mask++)
hhat[mask] = fhat[mask] * ghat[mask];
return fwht(hhat, n, 1);
}
Tương tự với phép gộp tập hợp, nếu muốn nhân nhiều hàm theo phép hiệu đối xứng, ta có thể biến đổi Walsh-Hadamard cho từng hàm, nhân giá trị tính được, rồi biến đổi Walsh-Hadamard ngược để nhận được hàm kết quả.
Nhìn chung, có thể thấy rằng các phép nhân các hàm trên tập hợp có đặc điểm chung là bao gồm
Bạn đọc nên tự thử sức trước với các bài tập dưới đây trước khi bước vào phần phân tích ý tưởng và cài đặt nhé.
Cho dãy
Với mọi bộ năm hợp lệ, hãy tính tổng:
với
Ta mặc định điều kiện thứ nhất luôn thỏa.
Từ điều kiện thứ hai, ta tách
Gọi
Từ đây, gọi
Với
Khi đó, đáp án cuối cùng là:
Bây giờ, ta sẽ tìm cách tính
Đối với nhóm đầu tiên, ta có công thức định nghĩa
Dễ thấy, phần
Đây là nhóm dễ xử lý nhất, ta có:
Với
Đối với nhóm thứ ba, ta có định nghĩa
Tương tự nhóm
Cuối cùng, ta thực hiện phép nhân gộp tập hợp trong
#include <bits/stdc++.h>
using namespace std;
const int mn = 1e6 + 6;
const int MOD = 1e9 + 7;
int add (int a, int b) { return a + b - (a + b < MOD ? 0 : MOD); }
int sub (int a, int b) { return a - b + (a - b >= 0 ? 0 : MOD); }
int mul (int a, int b) { return 1LL * a * b % MOD; }
int binpow (int a, int b) {
int ans = 1;
for (; b; b >>= 1, a = mul(a, a))
if (b & 1) ans = mul(ans, a);
return ans;
}
namespace convolutions {
// hàm biến đổi Walsh-Hadamard và biến đổi ngược
vector<int> fwht (const vector<int> &f, int n, bool inversed = 0) {
vector<int> dp = f;
for (int k = 0; k < n; k++) {
for (int mask = 0; mask < (1 << n); mask++) {
if (!(mask & (1 << k))) continue;
int u = dp[mask ^ (1 << k)], v = dp[mask];
dp[mask ^ (1 << k)] = add(u, v), dp[mask] = sub(u, v);
}
}
if (inversed) {
int inv = binpow(1 << n, MOD - 2);
for (int mask = 0; mask < (1 << n); mask++) dp[mask] = mul(dp[mask], inv);
}
return dp;
}
// hàm DP sum over subset/superset và DP ngược
vector<int> sos (const vector<int> &f, int n, bool subset, bool reversed = 0) {
vector<int> dp = f;
if (reversed) {
for (int k = n - 1; k >= 0; k--) {
for (int mask = 0; mask < (1 << n); mask++) {
bool flag = ((mask >> k & 1) == subset);
if (flag) dp[mask] = sub(dp[mask], dp[mask ^ (1 << k)]);
}
}
}
else {
for (int k = 0; k < n; k++) {
for (int mask = 0; mask < (1 << n); mask++) {
bool flag = ((mask >> k & 1) == subset);
if (flag) dp[mask] = add(dp[mask], dp[mask ^ (1 << k)]);
}
}
}
return dp;
}
// phép gộp tập hợp
vector<int> andConvolution (const vector<int> &f1, const vector<int> &f2, const vector<int> &f3, int n) {
vector<int> g1 = sos(f1, n, 0), g2 = sos(f2, n, 0), g3 = sos(f3, n, 0), hhat(1 << n);
for (int mask = 0; mask < (1 << n); mask++)
hhat[mask] = mul(g1[mask], mul(g2[mask], g3[mask]));
return sos(hhat, n, 0, 1);
}
// phép nhân tập con
vector<int> subsetConvolution (const vector<int> &f, const vector<int> &g, int n) {
vector<vector<int>> fhat(n + 1, vector<int>(1 << n)), ghat(n + 1, vector<int>(1 << n));
for (int mask = 0; mask < (1 << n); mask++) {
fhat[__builtin_popcount(mask)][mask] = f[mask];
ghat[__builtin_popcount(mask)][mask] = g[mask];
}
for (int i = 0; i <= n; i++)
fhat[i] = sos(fhat[i], n, 1), ghat[i] = sos(ghat[i], n, 1);
vector<vector<int>> hhat(n + 1, vector<int>(1 << n));
for (int i = 0; i <= n; i++)
for (int mask = 0; mask < (1 << n); mask++)
for (int j = 0; j <= i; j++)
hhat[i][mask] = add(hhat[i][mask], mul(fhat[j][mask], ghat[i - j][mask]));
for (int i = 0; i <= n; i++)
hhat[i] = sos(hhat[i], n, 1, 1);
vector<int> h(1 << n);
for (int mask = 0; mask < (1 << n); mask++)
h[mask] = hhat[__builtin_popcount(mask)][mask];
return h;
}
// phép hiệu đối xứng
vector<int> xorConvolution (const vector<int> &f, const vector<int> &g, int n) {
int sz = 1 << n;
vector<int> hhat(sz), fhat = fwht(f, n), ghat = fwht(g, n);
for (int mask = 0; mask < sz; mask++)
hhat[mask] = mul(fhat[mask], ghat[mask]);
return fwht(hhat, n, 1);
}
}
int fib[mn];
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
// tính số Fibonacci
fib[0] = 0, fib[1] = 1;
for (int i = 2; i < mn; i++) fib[i] = add(fib[i - 1], fib[i - 2]);
// đọc input và tạo mảng thống kê
int n = 17, m; cin >> m;
vector<int> freq(1 << n), g1, g2, g3;
for (int i = 0; i < m; i++) {
int a; cin >> a;
freq[a]++;
}
// tính g1(S)
g1 = convolutions::subsetConvolution(freq, freq, n);
for (int mask = 0; mask < (1 << n); mask++) g1[mask] = mul(g1[mask], fib[mask]);
// tính g2(S)
g2 = freq;
for (int mask = 0; mask < (1 << n); mask++) g2[mask] = mul(g2[mask], fib[mask]);
// tính g3(S)
g3 = convolutions::xorConvolution(freq, freq, n);
for (int mask = 0; mask < (1 << n); mask++) g3[mask] = mul(g3[mask], fib[mask]);
// tính h(S) và lấy kết quả
vector<int> h = convolutions::andConvolution(g1, g2, g3, n);
int ans = 0;
for (int i = 0; i < n; i++)
ans = add(ans, h[1 << i]);
cout << ans;
return 0;
}
Cho dãy
Để duyệt hai dãy con không có phần chung, ta có thể duyệt mọi tập con làm dãy con đầu tiên, sau đó duyệt mọi tập con của tập các vị trí chưa được chọn làm tập con thứ hai. Có thể thấy, ta đang chia dãy
Ta có thể tối ưu thuật toán hơn bằng cách đưa ra nhận xét là tổng XOR của hai dãy con này luôn bằng
Từ đó, ta có thể tối ưu thuật toán trên thành: Duyệt mọi dãy con của
Để dễ dàng hơn cho việc định nghĩa hàm sinh cho tập hợp, ta viết lại một hàm ánh xạ tập hợp
Một hàm ánh xạ tập hợp
Trong đó, ta gọi
Các phép toán được tìm hiểu ở phần trên (phép gộp tập hợp, nhân tập con và hiệu đối xứng) cũng được định nghĩa tương tự trên chuỗi lũy thừa tập hợp.
Giả sử, với
Như đã phân tích ở phần trên, với mỗi phần tử của dãy
Từ đây, ta có thể biến đổi các giá trị của dãy
Lúc này, ta cần tính số cách chọn sao cho tổng XOR của hai dãy con bằng
Đến đây ta đã có thuật toán
Tuy không thực hiện thuật toán FWHT nhưng ý tưởng của lời giải vẫn sẽ là thực hiện biến đổi Walsh-Hadamard trên từng hàm sinh
Biến đổi Walsh-Hadamard trên hàm sinh
Lúc đó, hàm
Để ý rằng tất cả các thừa số chỉ có thể nhận một trong hai giá trị:
Như vậy, với mọi tập
Sau đó, ta khôi phục hàm
Như vậy, nhiệm vụ còn lại chỉ còn là tính
Để ý rằng biến đổi Walsh-Hadamard trên hàm
Hơn nữa, ta biết rằng
Bên cạnh đó, mình cũng đã viết một lời giải tính
Như vậy, chúng ta đã giải bài toán bằng cách xây dựng hàm sinh, tính tích các hàm sinh theo phép hiệu đối xứng theo mô hình biến đổi Walsh-Hadamard. Tuy nhiên, do sự đặc biệt của các hàm sinh, ta không dùng FWHT mà biến đổi kết hợp nhận xét để xử lý.
Từ cách tính
Khi biến đổi Walsh-Hadamard trên hàm thống kê của một dãy số. Ta được hàm
Thuật toán cuối cùng của chúng ta có độ phức tạp
#include <bits/stdc++.h>
using namespace std;
const int MOD = 998'244'353;
int add (int a, int b) { return a + b - (a + b < MOD ? 0 : MOD); }
int sub (int a, int b) { return a - b + (a - b >= 0 ? 0 : MOD); }
int mul (int a, int b) { return 1LL * a * b % MOD; }
int binpow (int a, int b) {
int ans = 1;
for (; b; b >>= 1, a = mul(a, a))
if (b & 1) ans = mul(ans, a);
return ans;
}
vector<int> fwht (const vector<int> &f, int n) {
vector<int> dp = f;
for (int k = 0; k < n; k++) {
for (int mask = 0; mask < (1 << n); mask++) {
if (mask & (1 << k)) continue;
int u = dp[mask], v = dp[mask ^ (1 << k)];
dp[mask] = u + v, dp[mask ^ (1 << k)] = u - v;
}
}
return dp;
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
/// read input
int n; cin >> n;
vector<int> freq(1 << 17);
for (int i = 0; i < n; i++) {
int a; cin >> a;
freq[a]++;
}
/// Fast Walsh-Hadamard Transform on freq
vector<int> diff = fwht(freq, 17);
/// Walsh-Hadamard Transform on generating functions
int ans = 0;
for (int mask = 0; mask < (1 << 17); mask++) {
int even = (n + diff[mask]) >> 1, odd = n - even;
int wht = binpow(3, even);
if (odd & 1) wht = sub(0, wht);
ans = add(ans, wht);
}
/// compute answer
cout << mul(ans, binpow(1 << 17, MOD - 2));
return 0;
}