Recently I was trying to solve the following problem: 102441E - Very Simple Sum.
In process of solving it, I realised that I need to use xor convolution and just copied FWHT code somewhere from the internet. My solution passed, but I wanted to know how does it work, so started searching info on FWHT and xor convolution.
After some time of going through endless blogs talking about weird matrices and other difficult stuff, I decided to reinvent everything on my own, as I always do. Here I will describe a simple algorithmic way to look at xor convolution, I hope that it doesn't contain any crucial mistakes and will be useful for you.
The Algorithm
Let the size of the arrays be $$$2^n$$$, we want to calculate
for all $$$0\le i\le 2^n - 1$$$.
If we look at halves of the arrays separately, first half consists of indices with $$$n$$$-th bit set to zero, and the second consists of indices with $$$n$$$-th bit set to one, so the sum becomes
where $$$X0$$$ is the first half of $$$X$$$ and $$$X1$$$ is the second.
Let's take a look at the xor convolution of $$$A0+A1$$$ and $$$B0+B1$$$:
OMG! $$$D0_i = C0_i + C1_i$$$, now we just need to somehow get $$$C0$$$ and $$$C1$$$ out of $$$D0$$$. How to make different parts of the sum distinguishable from each other? Just add some minus signs and hope that everything will work out!
That's really cool. Now we can see that $$$C0_i = \frac{D0_i + D1_i}{2}$$$ and $$$C1_i = \frac{D0_i - D1_i}{2}$$$.
So the final algorithm is to recursively calculate $$$D0$$$ and $$$D1$$$ and then get $$$C0$$$ and $$$C1$$$ from them. There are $$$O(n)$$$ levels of recursion and $$$O(2^n)$$$ operations on each level, which gives us $$$O(n2^n)$$$ recursive algorithm.
Iterative Implementation and Interesting Results
Let's implement the same algorithm iterative way by computing everything in place. Also let's divide everything by $$$2^n$$$ in the end instead of dividing by $$$2$$$ every step. The implementation looks like this:
It's not hard to see that now the code does the following: transform a to special form; tranform b to special form; calculate c; tranform c from special form;
, so you can separate transformations into functions. I'm not sure if you can do more than one multiplication between transformations, but it's still impressive how simple all of this can be.
First time i understand what convolution is
Thanks!!
Also can you do it for other convolutions Also
xor ,or ,and many other
Dang this is really clean! I spent some time reading this blog a while ago (https://codeforces.net/blog/entry/115438) which I also found pretty clean.
It seems FWHT is useless because we can do AND/OR/XOR convolutions without it? I never learned it though, when I looked at some blog about it I was intimidated haha.
I now realize that this IS FWHT :face_palm:
Is it possible to do this with xor base 3? (Without the use of complex numbers)
3 seems harder than 2
Then again I didn't answer your question at all
credits: lrvideckis
seems like https://dmoj.ca/problem/coci21c1p4
true
You can use x^3 = 1 or x^3 — 1 = 0
So we have C0i = (D0i + D1i + D2i) / 3, C1i = (D0i + D1i * x + D2i * x^2) / 3, C2i = (D0i + D1i * x^2 + D2i * x^4) / 3, taking everything modulo x^3 — 1, or something similar. If you want a problem like that solve https://codeforces.net/problemset/problem/1103/E