[UOJ 310]Chocolate

Difficulty Ratings

Idea Creativity: 3/5
Techniques Used: 4/5
Implementation : 3/5
This time I will share some standard tricks which I learnt recently.

Simplified Statement

You have $N \le 1e6$ chocolates, each having value $ a_i < 2^M$, where $M = 20$. FInd the number of ways to choose two subsets of the chocolates $A$ and $B$ such that:
1) Their intersection is empty set.
2) The xor sum of elements in $A \cup B$ is $0$.
Find modulo $998244353$.

Solution

This problem screams Fast Walsh-Hadamard Transform (FWT). However, it is not obvious how to use it. For simplicity, let's define some symbols.
-$f(A)$ is the FWT of $A$.
-$f^{-1}(A)$ is the inverse FWT of $A$.
-$A \oplus B$ is the xor-convolution of $A$ and $B$.
-$A \cdot B$ is the dot-product of $A$ and $B$.
So we know that
-$f^{-1}(f(A) \cdot f(B)) = A \oplus B$
Also some properties are
-$f(A+B)=f(A)+f(B)$ (Same holds for $f^{-1}$ too.)
-$f^{-1}(f(A))=A$

So lets see how to use this. Define $A_i$ to be the array where all values are $0$ except $A_i[0]$, which is $1$ and $A_i[a_i]$, which is $2$. Then, the answer is the value of the $0-th$ element in $f^{-1}(f(A_1) \cdot f(A_2) \cdot f(A_3) \cdots f(A_n))$. Define $U$ to be $f(A_1) \cdot f(A_2) \cdot f(A_3) \cdots f(A_n)$. Obviously, directly evaluating that would result in TLE. Lets look into $f(A_i)$. We realise that the values of each element in the array is either $3$ or $-1$. So, lets take a position $j$, and lets say $x_j$ of them has $A_i[j]=3$ and $n-x_j$ of them has $A_i[j]=-1$. Then we know that $U[j]=3^{x_j} \times {-1}^{n-x_j}$.

Let's look at $f(A_1) + f(A_2) + f(A_3) \cdots f(A_n)$. Call it $V$. So we realise that $V = f(A_1 + A_2 + A_3 + \cdots A_n)$, so $V$ can be evaluated easily. Look closer to $V[j]$. We see that $V[j]=3 \times x_j + (-1) \times (n-x_j)$. That is very cool, because we can now find out $x_j$ quick, which means we can find $U$ quick too! It remains to compute $f^{-1}(U)[0]$ and we are done!

Comments

I think the idea of constructing $V$ is very interesting. I thought FWT problems are boring... You can also try CF 1119H, which is of similar topic.