Hello community!↵
So I guess most people here do not know about Fast Walsh-Hadamard Transform (FWHT), which is a beautiful algorithm. Its most famous feat is solving bitwise convolutions in O (N log N) time, a problem that would otherwise trap you in an O(N²) brute-force nightmare. If you've ever used Fast Fourier Transform (FFT) to multiply polynomials, FWHT is its hardcore, bit-manipulating cousin that operates directly in the realm of XOR,AND,and OR operations.↵
Today, we are going to dive straight to the bottom of the ocean—exploring the stunning mathematics behind FWHT and implementing a cache-friendly, ultra-optimized C++ template that works at the transistor level.↵
↵
here is the code which is O (N ^ 2) time complexity ↵
↵
↵
~~~~~↵
for (int i = 0; i < n; i++) {↵
for (int j = 0; j < n; j++) {↵
C[i ^ j] += A[i] * B[j]; ↵
}↵
}↵
~~~~~↵
↵
For the XOR operation, the transformation relies on the Hadamard Matrix ($H_n$). It is defined recursively as:↵
↵
$$H_0 = \begin{pmatrix} 1 \end{pmatrix}$$↵
↵
$$H_n = \begin{pmatrix} H_{n-1} & H_{n-1} \\ H_{n-1} & -H_{n-1} \end{pmatrix}$$↵
↵
For example, a $2 \times 2$ Hadamard matrix looks like this:↵
↵
$$H_1 = \begin{pmatrix} 1 & 1 \\ 1 & -1 \end{pmatrix}$$↵
↵
Why this specific matrix? Because its individual elements perfectly reflect the dot product of bits at the hardware level: ↵
↵
This innate symmetry fits the bitwise nature of XOR perfectly.↵
↵
↵
so here is our optimize code which is O (N log N)↵
↵
~~~~~↵
#include <vector>↵
#include <iostream>↵
↵
enum class BitOp { XOR, AND, OR };↵
↵
// In-place FWHT: O(N log N) time and O(1) auxiliary memory↵
void FWHT(std::vector<long long>& a, BitOp op, bool inverse) {↵
int n = a.size();↵
↵
// Linear iterative loops designed to maximize CPU pipeline efficiency↵
for (int len = 1; len < n; len <<= 1) {↵
for (int i = 0; i < n; i += (len << 1)) {↵
for (int j = 0; j < len; j++) {↵
long long u = a[i + j];↵
long long v = a[i + len + j];↵
↵
if (op == BitOp::XOR) {↵
if (!inverse) {↵
a[i + j] = u + v;↵
a[i + len + j] = u - v;↵
} else {↵
// Inverse XOR requires dividing by 2.↵
// Bit shifting (>> 1) takes exactly 1 clock cycle on standard CPUs!↵
a[i + j] = (u + v) >> 1;↵
a[i + len + j] = (u - v) >> 1;↵
}↵
} ↵
else if (op == BitOp::OR) {↵
a[i + len + j] = !inverse ? (u + v) : (v - u);↵
} ↵
else if (op == BitOp::AND) {↵
a[i + j] = !inverse ? (u + v) : (u - v);↵
}↵
}↵
}↵
}↵
}↵
↵
// Master function to execute the full Bitwise Convolution↵
std::vector<long long> bitwise_convolution(std::vector<long long> A, std::vector<long long> B, BitOp op) {↵
FWHT(A, op, false);↵
FWHT(B, op, false);↵
↵
for (size_t i = 0; i < A.size(); i++) {↵
A[i] *= B[i];↵
}↵
↵
FWHT(A, op, true); // Inverse transform back to original domain↵
return A;↵
}↵
~~~~~↵
↵
The reason that is faster than previous version is because of↵
↵
↵
**Bitwise Shift Arithmetic (`len <<= 1`):** We completely bypass slow assembly division or multiplication instructions by shifting bits directly left or right. It is the cheapest hardware instruction execution possible.↵
↵
↵
**Spatial Locality (Cache Friendliness):** The nested loops process indices linearly. The CPU's *Hardware Prefetcher* effortlessly predicts this stream, pulling data from RAM straight into the L1/L2 cache lines before the code even requests them. Cache misses drop to nearly zero.↵
↵
↵
OK, so we saw the template itself let's solve one problem:↵
↵
↵
Binary Table (https://codeforces.me/contest/662/problem/C)↵
↵
↵
time limit per test↵
↵
↵
6 seconds↵
↵
memory limit per test↵
↵
256 megabytes↵
↵
You are given a table consisting of n rows and m columns. Each cell of the table contains either 0 or 1. In one move, you are allowed to pick any row or any column and invert all values, that is, replace 0 by 1 and vice versa.↵
↵
What is the minimum number of cells with value 1 you can get after applying some number of operations?↵
↵
Input↵
The first line of the input contains two integers n and m (1 ≤ n ≤ 20, 1 ≤ m ≤ 100 000) — the number of rows and the number of columns, respectively.↵
↵
Then n lines follows with the descriptions of the rows. Each line has length m and contains only digits '0' and '1'.↵
↵
Output↵
Output a single integer — the minimum possible number of ones you can get after applying some sequence of operations.↵
↵
Example↵
↵
↵
InputCopy↵
↵
↵
3 4↵
↵
0110↵
↵
1010↵
↵
0111↵
↵
↵
OutputCopy↵
↵
2↵
↵
<spoiler summary="here is my code">↵
↵
~~~~~↵
↵
↵
#include <iostream>↵
#include <vector>↵
#include <string>↵
#include <algorithm>↵
↵
using namespace std;↵
using ll = long long;↵
↵
#define endl "\n"↵
↵
enum class BitOp { XOR, AND, OR };↵
↵
void FWHT(vector<ll>& a, bool inverse) {↵
int n = a.size();↵
for (int len = 1; len < n; len <<= 1) {↵
for (int i = 0; i < n; i += (len << 1)) {↵
for (int j = 0; j < len; j++) {↵
ll u = a[i + j];↵
ll v = a[i + len + j];↵
if (!inverse) {↵
a[i + j] = u + v;↵
a[i + len + j] = u - v;↵
}↵
else {↵
a[i + j] = (u + v) >> 1;↵
a[i + len + j] = (u - v) >> 1;↵
}↵
}↵
}↵
}↵
}↵
↵
int main() {↵
ios_base::sync_with_stdio(false);↵
cin.tie(NULL);↵
↵
int n, m;↵
cin >> n >> m;↵
vector<string> grid(n);↵
for (int i = 0; i < n; i++) {↵
cin >> grid[i];↵
}↵
int mask_cnt= 1 << n;↵
vector<ll> A(mask_cnt, 0);↵
for (int j = 0; j < m; j++) {↵
int mask = 0;↵
for (int i = 0; i < n; i++) {↵
if (grid[i][j] == '1') {↵
mask |= (1 << i);↵
}↵
}↵
A[mask]++;↵
}↵
vector<ll> B(mask_cnt, 0);↵
for (int i = 0; i < mask_cnt; i++) {↵
int bits = __builtin_popcount(i);↵
B[i] = min(bits, n - bits);↵
}↵
FWHT(A, false);↵
FWHT(B, false);↵
for (int i = 0; i < mask_cnt; i++) {↵
A[i] *= B[i];↵
}↵
FWHT(A, true);↵
ll ans = 1LL * n * m; ↵
for (int i = 0; i < mask_cnt; i++) {↵
ans = min(ans, A[i]);↵
}↵
cout << ans << endl;↵
↵
return 0;↵
}↵
↵
~~~~~↵
↵
</spoiler>↵
↵
To completely understand why this works, let's break down the logic step-by-step from raw formulas to the clean XOR convolution.↵
↵
Let $R$ be the bitmask representing our choices of row flips. If the $i$-th bit of $R$ is $1$, it means we flip the $i$-th row.↵
↵
If we apply the row flips $R$, any column whose initial configuration had a bitmask $mask$ will transform into a new configuration:↵
↵
$$\text{new\_mask} = mask \oplus R$$↵
↵
For this column, we want to minimize the number of ones. We can choose to either flip this column entirely or leave it as it is. ↵
↵
* If we do nothing, the number of 1s is: `popcount(mask XOR R)`↵
* If we flip the column, the number of 1s becomes: `N - popcount(mask XOR R)`↵
↵
To get the absolute minimum, we define a precomputed function $B[x]$:↵
↵
$$B[x] = \min(\text{popcount}(x), N - \text{popcount}(x))$$↵
↵
Thus, the number of $1$s contributed by a column with the shape $mask \oplus R$ is exactly $B[mask \oplus R]$.↵
↵
↵
↵
Let $A[mask]$ be the frequency array indicating how many columns in the given initial table have the exact bitmask $mask$. ↵
↵
For a fixed row flip choice $R$, the total number of $1$s in the entire table, $Total(R)$, is the sum of costs over all possible column masks:↵
$$Total(R) = \sum_{mask = 0}^{2^N - 1} A[mask] \cdot B[mask \oplus R]$$↵
↵
If we compute this directly for all $2^N$ possible row flip masks $R$, each taking $O(2^N)$ summation steps, the overall runtime becomes $O(2^N \cdot 2^N) = O(4^N)$. With $N = 20$, $4^{20} \approx 10^{12}$, which is too slow. We must optimize this expression.↵
↵
Let's introduce a new variable, $target$, to track the state after the bitwise operation. We define:↵
$$target = mask \oplus R$$↵
↵
Using the foundational properties of the XOR (\(\oplus\)) operation, we know that if $target = mask \oplus R$, then we can XOR both sides by $R$ to isolate $mask$:↵
$$mask = target \oplus R$$↵
↵
Now, let's substitute $mask$ inside our $Total(R)$ equation. The summation domain remains exactly the same ($0$ to $2^N - 1$) because XOR is a bijective permutation over the set of masks:↵
$$Total(R) = \sum_{target = 0}^{2^N - 1} A[target \oplus R] \cdot B[target]$$↵
↵
Because XOR is commutative ($target \oplus R = R \oplus target$), we can rewrite it as:↵
$$Total(R) = \sum_{target = 0}^{2^N - 1} A[R \oplus target] \cdot B[target]$$↵
↵
Look at the mathematical definition of a standard **Bitwise XOR Convolution** between two arrays $X$ and $Y$:↵
$$Z[k] = \sum_{i \oplus j = k} X[i] \cdot Y[j]$$↵
↵
By utilizing the properties of the Walsh-Hadamard Transform, this convolution can be computed instantaneously in the transformed frequency domain:↵
$$\text{FWHT}(Z) = \text{FWHT}(X) \cdot \text{FWHT}(Y)$$↵
↵
Our equation $Total(R) = \sum A[R \oplus target] \cdot B[target]$ fits this pattern perfectly! ↵
* Array $A$ acts as our first polynomial.↵
* Array $B$ acts as our second polynomial.↵
* The index $R$ acts as the target convolution bit state $k$.↵
↵
By applying the forward $\text{FWHT}$ to both frequency spectrum matrices $A$ and $B$, performing a linear $O(2^N)$ pointwise dot-product multiplication, and applying the Inverse $\text{FWHT}$ back, we obtain the $Total(R)$ answers for all $2^N$ row configurations simultaneously.↵
↵
$$\text{Final Complexity:} \quad O(N \cdot 2^N)$$↵
↵
so our topic's end is here, here is more problems for your practise and grow in this technique↵
↵
* **[Codeforces — 914G: Sum the Elements](https://codeforces.com)**↵
↵
* *Why solve it:* This is the ultimate test for bitwise convolutions. It requires you to simultaneously combine **AND**, **OR**, and **XOR** convolutions alongside Fibonacci numbers in a single problem.↵
↵
↵
* **[Codeforces — 1750E: Bracket Cost](https://codeforces.com)**↵
* *Why solve it:* A great problem to practice modeling state transitions that can be refactored into fast transform operations.↵
↵
↵
* **[SPOJ — MAXMATCH: Maximum Match](https://spoj.com)**↵
* *Why solve it:* An excellent introductory problem to practice array alignments and transitions before shifting to full bitwise domains.\↵
↵
* **[Codeforces — Yet Another String Matching Problem](https://codeforces.com)**↵
* *Why solve it:* Mixes string-matching algorithms with optimal polynomial representations, bridging standard FFT foundations with subset combinations.↵
↵
↵
* **[CodeChef — Expected Number of Customers](https://codechef.com)**↵
* *Why solve it:* Introduces probabilities and expected values over bitwise properties where FWHT accelerates otherwise impossible transitions.↵
* **[AtCoder — ABC 212 H: Nim Counting](https://atcoder.jp)**↵
* *Why solve it:* A phenomenal problem to practice FWHT combined with matrix exponentiation (polynomial power) to count winning Nim states.↵
* **[Codeforces — 1119H: Triple XOR](https://codeforces.com)**↵
* *Why solve it:* A legendary 3000-rated problem that pushes the properties of XOR convolution and linearity to their absolute mathematical limits.↵
* **[Codeforces — 582E: Boolean Expressions](https://codeforces.com)**↵
* *Why solve it:* Requires evaluating logical parsing trees using dynamic programming enhanced by AND/OR transforms.↵
* **[Codeforces — 1326F2: Wise Men (Hard Version)](https://codeforces.com)**↵
* *Why solve it:* A masterful challenge blending SOS DP (Sum of Over Subsets), inclusion-exclusion, and advanced bitwise properties.↵
* **[Yosupo Library Checker — Bitwise XOR Convolution](https://yosupo.jp)**↵
* *Why solve it:* The pure, unadulterated standard benchmark judge to test your template against optimal global constraints.↵
* **[Codeforces — 1494F: Delete The Edges](https://codeforces.com)**↵
* *Why solve it:* A heavy, graph-oriented problem that can be heavily optimized using SOS DP and submask transitions, serving as an elite training ground for bitwise properties.↵
* **[Codeforces — 1521E: Nastia and a Beautiful Matrix](https://codeforces.com)**↵
* *Why solve it:* Pushes your ability to re-order configuration components linearly under massive bounds, perfect for testing cache-friendly architectures.↵
↵
and do not forget to read this too :) -> (https://cp-algorithms.com/algebra/fft.html)↵
So I guess most people here do not know about Fast Walsh-Hadamard Transform (FWHT), which is a beautiful algorithm. Its most famous feat is solving bitwise convolutions in O (N log N) time, a problem that would otherwise trap you in an O(N²) brute-force nightmare. If you've ever used Fast Fourier Transform (FFT) to multiply polynomials, FWHT is its hardcore, bit-manipulating cousin that operates directly in the realm of XOR,AND,and OR operations.↵
Today, we are going to dive straight to the bottom of the ocean—exploring the stunning mathematics behind FWHT and implementing a cache-friendly, ultra-optimized C++ template that works at the transistor level.↵
↵
here is the code which is O (N ^ 2) time complexity ↵
↵
↵
~~~~~↵
for (int i = 0; i < n; i++) {↵
for (int j = 0; j < n; j++) {↵
C[i ^ j] += A[i] * B[j]; ↵
}↵
}↵
~~~~~↵
↵
For the XOR operation, the transformation relies on the Hadamard Matrix ($H_n$). It is defined recursively as:↵
↵
$$H_0 = \begin{pmatrix} 1 \end{pmatrix}$$↵
↵
$$H_n = \begin{pmatrix} H_{n-1} & H_{n-1} \\ H_{n-1} & -H_{n-1} \end{pmatrix}$$↵
↵
For example, a $2 \times 2$ Hadamard matrix looks like this:↵
↵
$$H_1 = \begin{pmatrix} 1 & 1 \\ 1 & -1 \end{pmatrix}$$↵
↵
Why this specific matrix? Because its individual elements perfectly reflect the dot product of bits at the hardware level: ↵
↵
This innate symmetry fits the bitwise nature of XOR perfectly.↵
↵
↵
so here is our optimize code which is O (N log N)↵
↵
~~~~~↵
#include <vector>↵
#include <iostream>↵
↵
enum class BitOp { XOR, AND, OR };↵
↵
// In-place FWHT: O(N log N) time and O(1) auxiliary memory↵
void FWHT(std::vector<long long>& a, BitOp op, bool inverse) {↵
int n = a.size();↵
↵
// Linear iterative loops designed to maximize CPU pipeline efficiency↵
for (int len = 1; len < n; len <<= 1) {↵
for (int i = 0; i < n; i += (len << 1)) {↵
for (int j = 0; j < len; j++) {↵
long long u = a[i + j];↵
long long v = a[i + len + j];↵
↵
if (op == BitOp::XOR) {↵
if (!inverse) {↵
a[i + j] = u + v;↵
a[i + len + j] = u - v;↵
} else {↵
// Inverse XOR requires dividing by 2.↵
// Bit shifting (>> 1) takes exactly 1 clock cycle on standard CPUs!↵
a[i + j] = (u + v) >> 1;↵
a[i + len + j] = (u - v) >> 1;↵
}↵
} ↵
else if (op == BitOp::OR) {↵
a[i + len + j] = !inverse ? (u + v) : (v - u);↵
} ↵
else if (op == BitOp::AND) {↵
a[i + j] = !inverse ? (u + v) : (u - v);↵
}↵
}↵
}↵
}↵
}↵
↵
// Master function to execute the full Bitwise Convolution↵
std::vector<long long> bitwise_convolution(std::vector<long long> A, std::vector<long long> B, BitOp op) {↵
FWHT(A, op, false);↵
FWHT(B, op, false);↵
↵
for (size_t i = 0; i < A.size(); i++) {↵
A[i] *= B[i];↵
}↵
↵
FWHT(A, op, true); // Inverse transform back to original domain↵
return A;↵
}↵
~~~~~↵
↵
The reason that is faster than previous version is because of↵
↵
↵
**Bitwise Shift Arithmetic (`len <<= 1`):** We completely bypass slow assembly division or multiplication instructions by shifting bits directly left or right. It is the cheapest hardware instruction execution possible.↵
↵
↵
**Spatial Locality (Cache Friendliness):** The nested loops process indices linearly. The CPU's *Hardware Prefetcher* effortlessly predicts this stream, pulling data from RAM straight into the L1/L2 cache lines before the code even requests them. Cache misses drop to nearly zero.↵
↵
↵
OK, so we saw the template itself let's solve one problem:↵
↵
↵
Binary Table (https://codeforces.me/contest/662/problem/C)↵
↵
↵
time limit per test↵
↵
↵
6 seconds↵
↵
memory limit per test↵
↵
256 megabytes↵
↵
You are given a table consisting of n rows and m columns. Each cell of the table contains either 0 or 1. In one move, you are allowed to pick any row or any column and invert all values, that is, replace 0 by 1 and vice versa.↵
↵
What is the minimum number of cells with value 1 you can get after applying some number of operations?↵
↵
Input↵
The first line of the input contains two integers n and m (1 ≤ n ≤ 20, 1 ≤ m ≤ 100 000) — the number of rows and the number of columns, respectively.↵
↵
Then n lines follows with the descriptions of the rows. Each line has length m and contains only digits '0' and '1'.↵
↵
Output↵
Output a single integer — the minimum possible number of ones you can get after applying some sequence of operations.↵
↵
Example↵
↵
↵
InputCopy↵
↵
↵
3 4↵
↵
0110↵
↵
1010↵
↵
0111↵
↵
↵
OutputCopy↵
↵
2↵
↵
<spoiler summary="here is my code">↵
↵
~~~~~↵
↵
↵
#include <iostream>↵
#include <vector>↵
#include <string>↵
#include <algorithm>↵
↵
using namespace std;↵
using ll = long long;↵
↵
#define endl "\n"↵
↵
enum class BitOp { XOR, AND, OR };↵
↵
void FWHT(vector<ll>& a, bool inverse) {↵
int n = a.size();↵
for (int len = 1; len < n; len <<= 1) {↵
for (int i = 0; i < n; i += (len << 1)) {↵
for (int j = 0; j < len; j++) {↵
ll u = a[i + j];↵
ll v = a[i + len + j];↵
if (!inverse) {↵
a[i + j] = u + v;↵
a[i + len + j] = u - v;↵
}↵
else {↵
a[i + j] = (u + v) >> 1;↵
a[i + len + j] = (u - v) >> 1;↵
}↵
}↵
}↵
}↵
}↵
↵
int main() {↵
ios_base::sync_with_stdio(false);↵
cin.tie(NULL);↵
↵
int n, m;↵
cin >> n >> m;↵
vector<string> grid(n);↵
for (int i = 0; i < n; i++) {↵
cin >> grid[i];↵
}↵
int mask_cnt= 1 << n;↵
vector<ll> A(mask_cnt, 0);↵
for (int j = 0; j < m; j++) {↵
int mask = 0;↵
for (int i = 0; i < n; i++) {↵
if (grid[i][j] == '1') {↵
mask |= (1 << i);↵
}↵
}↵
A[mask]++;↵
}↵
vector<ll> B(mask_cnt, 0);↵
for (int i = 0; i < mask_cnt; i++) {↵
int bits = __builtin_popcount(i);↵
B[i] = min(bits, n - bits);↵
}↵
FWHT(A, false);↵
FWHT(B, false);↵
for (int i = 0; i < mask_cnt; i++) {↵
A[i] *= B[i];↵
}↵
FWHT(A, true);↵
ll ans = 1LL * n * m; ↵
for (int i = 0; i < mask_cnt; i++) {↵
ans = min(ans, A[i]);↵
}↵
cout << ans << endl;↵
↵
return 0;↵
}↵
↵
~~~~~↵
↵
</spoiler>↵
↵
To completely understand why this works, let's break down the logic step-by-step from raw formulas to the clean XOR convolution.↵
↵
Let $R$ be the bitmask representing our choices of row flips. If the $i$-th bit of $R$ is $1$, it means we flip the $i$-th row.↵
↵
If we apply the row flips $R$, any column whose initial configuration had a bitmask $mask$ will transform into a new configuration:↵
↵
$$\text{new\_mask} = mask \oplus R$$↵
↵
For this column, we want to minimize the number of ones. We can choose to either flip this column entirely or leave it as it is. ↵
↵
* If we do nothing, the number of 1s is: `popcount(mask XOR R)`↵
* If we flip the column, the number of 1s becomes: `N - popcount(mask XOR R)`↵
↵
To get the absolute minimum, we define a precomputed function $B[x]$:↵
↵
$$B[x] = \min(\text{popcount}(x), N - \text{popcount}(x))$$↵
↵
Thus, the number of $1$s contributed by a column with the shape $mask \oplus R$ is exactly $B[mask \oplus R]$.↵
↵
↵
↵
Let $A[mask]$ be the frequency array indicating how many columns in the given initial table have the exact bitmask $mask$. ↵
↵
For a fixed row flip choice $R$, the total number of $1$s in the entire table, $Total(R)$, is the sum of costs over all possible column masks:↵
$$Total(R) = \sum_{mask = 0}^{2^N - 1} A[mask] \cdot B[mask \oplus R]$$↵
↵
If we compute this directly for all $2^N$ possible row flip masks $R$, each taking $O(2^N)$ summation steps, the overall runtime becomes $O(2^N \cdot 2^N) = O(4^N)$. With $N = 20$, $4^{20} \approx 10^{12}$, which is too slow. We must optimize this expression.↵
↵
Let's introduce a new variable, $target$, to track the state after the bitwise operation. We define:↵
$$target = mask \oplus R$$↵
↵
Using the foundational properties of the XOR (\(\oplus\)) operation, we know that if $target = mask \oplus R$, then we can XOR both sides by $R$ to isolate $mask$:↵
$$mask = target \oplus R$$↵
↵
Now, let's substitute $mask$ inside our $Total(R)$ equation. The summation domain remains exactly the same ($0$ to $2^N - 1$) because XOR is a bijective permutation over the set of masks:↵
$$Total(R) = \sum_{target = 0}^{2^N - 1} A[target \oplus R] \cdot B[target]$$↵
↵
Because XOR is commutative ($target \oplus R = R \oplus target$), we can rewrite it as:↵
$$Total(R) = \sum_{target = 0}^{2^N - 1} A[R \oplus target] \cdot B[target]$$↵
↵
Look at the mathematical definition of a standard **Bitwise XOR Convolution** between two arrays $X$ and $Y$:↵
$$Z[k] = \sum_{i \oplus j = k} X[i] \cdot Y[j]$$↵
↵
By utilizing the properties of the Walsh-Hadamard Transform, this convolution can be computed instantaneously in the transformed frequency domain:↵
$$\text{FWHT}(Z) = \text{FWHT}(X) \cdot \text{FWHT}(Y)$$↵
↵
Our equation $Total(R) = \sum A[R \oplus target] \cdot B[target]$ fits this pattern perfectly! ↵
* Array $A$ acts as our first polynomial.↵
* Array $B$ acts as our second polynomial.↵
* The index $R$ acts as the target convolution bit state $k$.↵
↵
By applying the forward $\text{FWHT}$ to both frequency spectrum matrices $A$ and $B$, performing a linear $O(2^N)$ pointwise dot-product multiplication, and applying the Inverse $\text{FWHT}$ back, we obtain the $Total(R)$ answers for all $2^N$ row configurations simultaneously.↵
↵
$$\text{Final Complexity:} \quad O(N \cdot 2^N)$$↵
↵
so our topic's end is here, here is more problems for your practise and grow in this technique↵
↵
* **[Codeforces — 914G: Sum the Elements](https://codeforces.com)**↵
↵
* *Why solve it:* This is the ultimate test for bitwise convolutions. It requires you to simultaneously combine **AND**, **OR**, and **XOR** convolutions alongside Fibonacci numbers in a single problem.↵
↵
↵
* **[Codeforces — 1750E: Bracket Cost](https://codeforces.com)**↵
* *Why solve it:* A great problem to practice modeling state transitions that can be refactored into fast transform operations.↵
↵
↵
* **[SPOJ — MAXMATCH: Maximum Match](https://spoj.com)**↵
* *Why solve it:* An excellent introductory problem to practice array alignments and transitions before shifting to full bitwise domains.\↵
↵
* **[Codeforces — Yet Another String Matching Problem](https://codeforces.com)**↵
* *Why solve it:* Mixes string-matching algorithms with optimal polynomial representations, bridging standard FFT foundations with subset combinations.↵
↵
↵
* **[CodeChef — Expected Number of Customers](https://codechef.com)**↵
* *Why solve it:* Introduces probabilities and expected values over bitwise properties where FWHT accelerates otherwise impossible transitions.↵
* **[AtCoder — ABC 212 H: Nim Counting](https://atcoder.jp)**↵
* *Why solve it:* A phenomenal problem to practice FWHT combined with matrix exponentiation (polynomial power) to count winning Nim states.↵
* **[Codeforces — 1119H: Triple XOR](https://codeforces.com)**↵
* *Why solve it:* A legendary 3000-rated problem that pushes the properties of XOR convolution and linearity to their absolute mathematical limits.↵
* **[Codeforces — 582E: Boolean Expressions](https://codeforces.com)**↵
* *Why solve it:* Requires evaluating logical parsing trees using dynamic programming enhanced by AND/OR transforms.↵
* **[Codeforces — 1326F2: Wise Men (Hard Version)](https://codeforces.com)**↵
* *Why solve it:* A masterful challenge blending SOS DP (Sum of Over Subsets), inclusion-exclusion, and advanced bitwise properties.↵
* **[Yosupo Library Checker — Bitwise XOR Convolution](https://yosupo.jp)**↵
* *Why solve it:* The pure, unadulterated standard benchmark judge to test your template against optimal global constraints.↵
* **[Codeforces — 1494F: Delete The Edges](https://codeforces.com)**↵
* *Why solve it:* A heavy, graph-oriented problem that can be heavily optimized using SOS DP and submask transitions, serving as an elite training ground for bitwise properties.↵
* **[Codeforces — 1521E: Nastia and a Beautiful Matrix](https://codeforces.com)**↵
* *Why solve it:* Pushes your ability to re-order configuration components linearly under massive bounds, perfect for testing cache-friendly architectures.↵
↵
and do not forget to read this too :) -> (https://cp-algorithms.com/algebra/fft.html)↵
