Wow, and this approach almost trivializes subset convolution. Now I can do subset convolution without any complicated tutorial :)

I think it works in any lattice, that is a set with a $$$\leq$$$ relation (partially ordered set) with a "least common ancestor" $$$i \wedge j$$$ and a "highest common descendent" $$$i \vee j$$$. We can kind of interpret them as follows:

• $$$i \wedge j$$$ as the maximum element that is less or equal than both $$$i$$$ and $$$j$$$, i.e. similar to $$$\min(i, j)$$$, $$$\gcd(i, j)$$$ or $$$i \cap j$$$,
• $$$i \vee j$$$ as the minimum element that is greater or equal than both $$$i$$$ and $$$j$$$, i.e. similar to $$$\max(i, j)$$$, $$$\operatorname{lcm}(i, j)$$$ or $$$i \cup j$$$.

In this notion, for $$$C[k]$$$ defined as

it always holds that

And you can always inverse the sum over $$$t \leq k$$$ via Möbius inversion formula as

where

is the Möbius function of the poset. See also this article by nor which extensively goes into the topic from poset point of view.

I think, this approach is generally known to CP community, as there are problems about GCD/LCM convolutions on Library Checker, but maybe it's not standard to use it in tutorials because tutorial authors perceive polynomial evaluation/interpolation, or sometimes matrix Kronecker product as more natural, insightful and relatable to cpers than the poset point of view?

Besides, these tutorials are usually written in a way that is supposed to be uniform for OR convolution, AND convolution and XOR convolution, and as you pointed it out yourself it doesn't work with XOR convolution.

super straightforward approach, I love it.

"Does nobody really know this?" — it's certainly the way I always thought about it and I didn't even know that it has any FWHT/FFT connections xd

I still don't know what FWHT is...

1. This looks amazing
2. Can you do non-binary base xor convolution, please mister legendary grandmaster?

There is a super nice and general way to view all kinds of transforms that are used for different kinds of convolution. The trick is to think about properties (functions) $$$f$$$ such that $$$f(A) \cdot f(B) = f(conv(A,B))$$$. In your example of OR-convolution, the proprties you are using are $$$f_0,...,f_{2^n-1}$$$ where $$$f_j(A) := \sum_{i \subseteq j} A[i]$$$.

Let's as another example take circular convolution with periodicity $$$n$$$. Meaning you are given two polynomials $$$A(x)$$$ and $$$B(x)$$$, and your goal is to find the polynomial $$$A(x) := B(x) \cdot C(x) \pmod{x^n - 1}$$$, which is an $$$(n-1)$$$-degree polynomial.

Note that for any complex number $$$\omega$$$ such that $$$\omega^n = 1$$$, we have that $$$A(\omega) \cdot B(\omega) = C(\omega)$$$. There are $$$n$$$ such complex numbers, and $$$C$$$ is an $$$(n - 1)$$$-degree polynomial. This means that by evaluating $$$A$$$ and $$$B$$$ in all of the $$$\omega$$$:s we have enough information to calculate $$$C$$$ using interpolation. The properties "$$$f$$$" that we are using here is the evaluation of a polynomial at the $$$\omega$$$:s.

So what is FFT? If you give FFT a $$$(n-1)$$$-degree polynomial, then it evaluates the polynomial in all $$$n$$$-th roots of unity (the $$$\omega$$$:s). Inverse FFT is the reverse of this, it finds a $$$(n-1)$$$-degree polynomial using interpolation. So if you have FFT and IFFT implemented, then it is trivial to implement circular convolution.

Here is an example of a Python implemention of circular convolution using FFT.

# Input:
# Two (n-1)-degree polynomials A and B.
# Integer n.
#
# Output:
# C := A * B (mod x^n - 1) 

def circular_convolution(A, B, n):
    assert n == len(A) == len(B)
    A_eval = FFT(A)
    B_eval = FFT(B)
    C_eval = [Aw*Bw for Aw,Bw in zip(A_eval, B_eval)]
    C = IFFT(C_eval)
    return C

What for uncommon people like us?

Thanks for the easy to understand blog — it is clearly another step in the right direction since it provides more evidence for the claim that all problems can be solved using DP.

You may also consider what you did (specifically sum-of-subset) as if you calculated the following DP: dp[b][i] is sum of $$$f(j)$$$ over all $$$j$$$ so that $$$j$$$ is a subset of $$$i$$$ and may differ only in the last (or first, doesn't matter) $$$b$$$ bits. Do you know how to calculate dp[b][i] from dp[b - 1][*]? Yes, if the $$$b$$$-th bit of $$$i$$$ is zero, then these values coincide, otherwise dp[b][i] = dp[b - 1][i] + dp[b - 1][i - (1 << b)]. Your two-cycles is computing this dp on one layer.

Keeping this in mind, you may generalize this to xor-convolution. Indeed, let dp[b][i] be the sum of $$$f(j)$$$ over $$$j$$$ that only differ from $$$i$$$ in the last $$$b$$$ bits, but also each $$$f(j)$$$ is multiplied by $$$-1$$$ if the number of bits they differ in is odd. Now I think you also know how to compute dp[b][i] from dp[b - 1][*].

Idk if this makes any visual sense to you, but probably it is easier to understand xor-convolution in terms of dp

Number of legend's comment in this blog >>>>>>>>>>>

Do not read this article if you are not red. Go solve binary search instead.

Wow FMT&FWT!

Cool! I used this technique to solve these problems:

• https://codeforces.net/contest/449/problem/D
• https://codeforces.net/group/qcIqFPYhVr/contest/203881/problem/K

You'll have to join this group for the second one.

Thank you for writing such a clear and concise blog.

What is this set notation in your summation ($$$\sum$$$) notation? Apologies if the question is duplicate or too noob.

I don't know if anybody care but its a small optimisation. We can get rid of the if statment by iterating over subset. you can read about Subset iteration here.

for (int i = 0; i < n; i++) {
  for (int j = 0; j < (1 << n); j++) {
    if ((j >> i) & 1) {
      A[j] += A[j - (1 << i)];
      B[j] += B[j - (1 << i)];
    }
  }
}

My Submission for AND Convolution using this Implementation. This approach reduces the runtime by a factor of 2.

for (int i = 0; i < n; i++) {
   const int S=(1<<n)-(1<<i)-1;
   int j=0;
   do{
      A[j + (1 << i)] += A[j];
      B[j + (1 << i)] += B[j];
      j = ((j | ~S) + 1) & S;// subset forward iteration
      /*
        j = (j-1) & S ; //subset Backward  iteration
        // When inner loop is like:: for (int j = (1<<n)-1; j >= 0; j--)
     */
   } while(j>0)
}

Do I need this to reach specialist or expert?

thanks so much for this post and pajenegod for his additions

i learned lots! its so neat that this idea works on so many different convolutions with only slight changes