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à bằng FWHT, ta tính bằng cách nhân hệ số:
Vấn đề cuối cùng chưa được giải quyết là làm cách nào để khôi phục từ . Nói cách khác, làm thế nào để biến đổi Walsh-Hadamard ngượ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 thành một vector , gọi là . Khi đó, vector được tính qua phép nhân ma trận:
với là ma trận Hadamard bậc .
Để khôi phục từ , ta cần tính . May mắn thay, với tính chất đặc biệt của ma trận Hadamard, ma trận Hadamard nghịch đảo chính là ma trận Hadamard chia cho . Tức là ta chỉ việc tính:
Như vậy, để khôi phục từ , ta thực hiện biến đổi Walsh-Hadamard trên rồi chia mọi hệ số của hàm đã được biến đổi cho .
Đố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 làm đáp án.
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 và để tính cùng một lúc.
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ước chính: biến đổi (DP SoS), nhân hệ số, biến đổi ngược (DP SoS ngược). Tùy vào đặc điểm và tính chất của từng phép nhân, ta sẽ biến đổi công thức để đưa về các mô hình liên quan đến bài toán Sum over Subsets để tận dụng tốc độ của thuật toán này.
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 gồm phần tử. Định nghĩa một bộ năm số nguyên là hợp lệ nếu:
Với mọi bộ năm hợp lệ, hãy tính tổng:
với là số Fibonacci thứ được định nghĩa như sau:
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 thành 3 nhóm để xử lý riêng, gồm: nhóm , nhóm , và nhóm .
Gọi lần lượt là (với ), và . Lúc này, ta cần tính:
Từ đây, gọi là tổng các thỏa đề bài sao cho , ta có thể tìm đáp án bằng cách tính hàm :
Với là phép nhân gộp tập hợp theo bitwise AND (AND Convolution) theo định nghĩa ở phần trên. Hàm cho biết tổng các tích fibonacci thỏa , nói cách khác:
Khi đó, đáp án cuối cùng là:
Bây giờ, ta sẽ tìm cách tính cho từng nhóm:
Đối với nhóm đầu tiên, ta có công thức định nghĩa là:
Dễ thấy, phần có thể được tính bằng phép nhân tập con (subset sum convolution) được định nghĩa ở trên trong .
Đây là nhóm dễ xử lý nhất, ta có:
Với là mảng thống kê trên dãy ban đầu.
Đối với nhóm thứ ba, ta có định nghĩa là:
Tương tự nhóm , phần có thể được tính bằng phép hiệu đối xứng (XOR convolution) trong .
Cuối cùng, ta thực hiện phép nhân gộp tập hợp trong . Như vậy, thuật toán có độ phức tạp .
#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 gồm phần tử. Đếm số cách chọn hai dãy con không có phần chung (có thể chọn tập rỗng) sao cho tổng XOR của hai dãy con này là bằng nhau. In đáp án modulo .
Tổng XOR của một dãy là .
Để 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 thành tập: các phần tử được chọn cho dãy con thứ nhất, các phần tử được chọn cho dãy con thứ hai và các phần tử không được chọn cho tập nào. Độ phức tạp của thuật toán này là .
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 . Hơn nữa, khi có một dãy số có tổng XOR bằng , mọi cách tách dãy số này ra thành hai phần không giao nhau đều cho ra hai dãy có tổng XOR bằng nhau. Ta có cách tách một dãy số có phần tử.
Từ đó, ta có thể tối ưu thuật toán trên thành: Duyệt mọi dãy con của , gọi là , nếu tổng XOR của chúng là , tăng đáp án lên .
Để 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 (với là ký hiệu tập các tập con của ) dưới dạng chuỗi lũy thừa tập hợp (set power series) như sau:
Một hàm ánh xạ tập hợp có thể được viết lại dưới dạng:
Trong đó, ta gọi là hệ số của số hạng .
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 và hàm ánh xạ là , , và . Ta có chuỗi lũy thừa tập hợp tương ứng là:
Như đã phân tích ở phần trên, với mỗi phần tử của dãy , gọi là , ta có cách chọn trạng thái cho nó:
Từ đây, ta có thể biến đổi các giá trị của dãy thành tập hợp dựa trên biểu diễn nhị phân và xây dựng hàm sinh cho mỗi phần tử:
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ói cách khác, ta cần tính hàm là tích của các hàm sinh theo phép hiệu đối xứng. Đáp án khi đó sẽ là hệ số của số hạng .
Đến đây ta đã có thuật toán nếu nhân bằng thuật trâu (với ). Lưu ý rằng do số lượng số hạng có hệ số khác của từng hàm sinh là rất thấp nên việc áp dụng Fast Walsh-Hadamard Transform trực tiếp lên hàm sinh trong trường hợp này thậm chí còn làm chậm tốc độ chương trình.
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 nhưng theo một cách khác.
Biến đổi Walsh-Hadamard trên hàm sinh sẽ cho ra hàm (được viết dưới dạng hàm ánh xạ) như sau:
Lúc đó, hàm (được viết dưới dạng hàm ánh xạ) là:
Để ý 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 (với ), nếu ta tính được số lượng sao cho là chẵn/lẻ, gọi là và , công thức tính trở thành:
Sau đó, ta khôi phục hàm từ bằng biến đổi Walsh-Hadamard ngược. Lúc này ta cũng không cần sử dụng FWHT vì ta chỉ cần , mà:
Như vậy, nhiệm vụ còn lại chỉ còn là tính cho mọi tập .
Để ý rằng biến đổi Walsh-Hadamard trên hàm (với là số sao cho ) sẽ cho ta biết hiệu với mọi tập . Điều này đúng vì các số mũ chẵn sẽ cho ra số hạng dương, và ngược lại, số mũ lẽ cho ra số hạng âm. Cụ thể
Hơn nữa, ta biết rằng luôn là . Từ đó, ta có thể tính như sau:
Bên cạnh đó, mình cũng đã viết một lời giải tính sử dụng DP SoS và tổ hợp. Bạn đọc có thể tham khảo code tại đây.
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 của bài toán trên, ta có thể đưa ra một nhận xét về biến đổi Walsh-Hadamard như sau:
Khi biến đổi Walsh-Hadamard trên hàm thống kê của một dãy số. Ta được hàm sao cho là số phần tử khi thực hiện bitwise AND với có số bit bật chẵn trừ đi số phần tử khi thực hiện bitwise AND với có số bit bật lẻ.
Thuật toán cuối cùng của chúng ta có độ phức tạp và phần cài đặt ngắn (so với lời giải) một cách bất ngờ!
#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;
}