Chiori and Doll Picking (hard version)
Contest: Codeforces Round 635 (Div. 1)
Difficulty rating: 3500
Tags: bitmasks, brute force, combinatorics, math

This is the hard version of the problem. The only difference between easy and hard versions is the constraint of $$$m$$$. You can make hacks only if both versions are solved.

Chiori loves dolls and now she is going to decorate her bedroom!

As a doll collector, Chiori has got $$$n$$$ dolls. The $$$i$$$-th doll has a non-negative integer value $$$a_i$$$ ($$$a_i < 2^m$$$, $$$m$$$ is given). Chiori wants to pick some (maybe zero) dolls for the decoration, so there are $$$2^n$$$ different picking ways.

Let $$$x$$$ be the bitwise-xor-sum of values of dolls Chiori picks (in case Chiori picks no dolls $$$x = 0$$$). The value of this picking way is equal to the number of $$$1$$$-bits in the binary representation of $$$x$$$. More formally, it is also equal to the number of indices $$$0 \leq i < m$$$, such that $$$\left\lfloor \frac{x}{2^i} \right\rfloor$$$ is odd.

Tell her the number of picking ways with value $$$i$$$ for each integer $$$i$$$ from $$$0$$$ to $$$m$$$. Due to the answers can be very huge, print them by modulo $$$998\,244\,353$$$.

Input format:
The first line contains two integers $$$n$$$ and $$$m$$$ ($$$1 \le n \le 2 \cdot 10^5$$$, $$$0 \le m \le 53$$$)  — the number of dolls and the maximum value of the picking way.

The second line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \le a_i < 2^m$$$)  — the values of dolls.

Output format:
Print $$$m+1$$$ integers $$$p_0, p_1, \ldots, p_m$$$  — $$$p_i$$$ is equal to the number of picking ways with value $$$i$$$ by modulo $$$998\,244\,353$$$.

Constraints:
Time limit: 3.0 s
Memory limit: 512.0 MB

Example input:
4 4
3 5 8 14

Example output:
2 2 6 6 0

Example input:
6 7
11 45 14 9 19 81

Example output:
1 2 11 20 15 10 5 0

Editorial:
Build linear basis $$$A$$$ with given numbers. Suppose:
• $$$k$$$ is the length of $$$A$$$.
• $$$S(A)$$$ is the set consisted of numbers which can be produced in $$$A$$$.
• $$$p_i$$$ is equal to the number of $$$x$$$, where $$$x \in S(A)$$$ and $$$\text{popcount}(x)=i$$$.
• $$$ans_i$$$ is equal to the number of doll picking ways with value $$$i$$$. Thus, $$$ans_i = p_i \cdot 2^{n-k}$$$.
Algorithm 1
Enumerate each base of $$$A$$$ is picked or not, so you can find out the whole $$$S(A)$$$ in $$$O(2^k)$$$ and get $$$p_0 \ldots p_m$$$. Note that you should implement $$$\text{popcount}(x)$$$ in $$$O(1)$$$ to make sure the whole algorithm runs in $$$O(2^k)$$$.
Algorithm 2
Let's assume the highest $$$1$$$-bits in every base are key bits, so in $$$A$$$ there are $$$k$$$ key bits and $$$m-k$$$ non-key bits. We can get a new array of bases by Gauss-Jordan Elimination, such that every key bit is $$$1$$$ in exactly one base and is $$$0$$$ in other bases.
Then, let $$$f_{i,j,s}$$$ be if we consider the first $$$i$$$ bases in $$$A$$$, the number of ways that $$$j$$$ key bits are $$$1$$$ in xor-sum and the binary status of all non-key bits is $$$s$$$. Enumerate $$$i$$$-th base (suppose it is equal to $$$x$$$) is picked or not, we write the state transition: $$$f_{i,j,s} = f_{i-1,j,s}+f_{i-1,j-1,s \oplus x}$$$.
At last, we add up $$$f_{k,j,s}$$$ to $$$p_{j+\text{popcount}(s)}$$$. In conclusion, we get an $$$O(k^2 \cdot 2^{m-k})$$$ algorithm.
So far, the easy version can be passed if you write a solution which runs Algorithm 1 or Algorithm 2 by the value of $$$k$$$.
Algorithm 3
We can regard $$$A$$$ as a $$$2^m$$$ long zero-indexation array satisfying $$$a_i=[i \in S(A)]$$$. Similarly, we define a $$$2^m$$$ long zero-indexation array $$$F^c$$$ satisfying $$$f^c_i=[\text{popcount}(i)=c]$$$.
By XOR Fast Walsh-Hadamard Transform, we calculate $$$\text{IFWT}(\text{FWT}(A) * \text{FWT}(F^c))$$$ (also can be written as $$$A \oplus F^c$$$). $$$p_c$$$ is equal to the $$$0$$$-th number of resulting array. That means $$$p_c$$$ is also equal to the sum of every number in $$$\text{FWT}(A) * \text{FWT}(F^c)$$$ divide $$$2^m$$$.
Lemma 1: $$$\text{FWT}(A)$$$ only contains two different values: $$$0$$$ and $$$2^k$$$.
Proof: The linear space satisfies closure, which means $$$A \oplus A = A * 2^k$$$. Thus, $$$\text{FWT}(A) * \text{FWT}(A) = \text{FWT}(A) * 2^k$$$. We can proved the lemma by solving an equation.
Lemma 2: The $$$i$$$-th number of $$$\text{FWT}(A)$$$ is $$$2^k$$$, if and only if $$$\text{popcount}(i\ \&\ x)$$$ is always even, where $$$x$$$ is any of $$$k$$$ bases in $$$A$$$.
Proof: XOR Fast Walsh-Hadamard Transform tells us, the $$$i$$$-th number of $$$\text{FWT}(A)$$$ is equal to the sum of $$$(-1)^{\text{popcount}(i\ \&\ j)}$$$ for each $$$j \in S(A)$$$. Once we find a base $$$x$$$ such that $$$\text{popcount}(i\ \&\ x)$$$ is odd, the sum must be $$$0$$$ according to Lemma 1.
Lemma 3: The indices of $$$\text{FWT}(A)$$$ which their values are $$$2^k$$$, compose an orthogonal linear basis.
Proof: See Lemma 2. If $$$\text{popcount}(i\ \&\ x)$$$ is even, $$$\text{popcount}(j\ \&\ x)$$$ is even, obviously $$$\text{popcount}((i \oplus j)\ \&\ x)$$$ is even.
Lemma 4: Suppose $$$B$$$ is the orthogonal linear basis. The length of $$$B$$$ is $$$m-k$$$.
Proof: We know that $$$A=\text{IFWT}(B*2^k)$$$, so $$$a_0 = 1 = \dfrac{1}{2^m}\sum\limits_{i=0}^{2^m-1} b_i \cdot 2^k$$$. From this, we then find that $$$|S(B)|$$$ should be $$$2^{m-k}$$$, which means the length of $$$B$$$ is $$$m-k$$$.
Let the key bits in $$$A$$$ are non-key bits in $$$B$$$ and the non-key bits in $$$A$$$ are key bits in $$$B$$$. Now I'll show you how to get the $$$m-k$$$ bases in $$$B$$$. Divide key bits for $$$A$$$ and put them to the left. Similarly, we put the key bits in $$$B$$$ to the right. Let's make those $$$1$$$ key bits form a diagonal.
Look at the following picture. Do you notice that the non-key bit matrices (green areas) are symmetrical along the diagonal?
The proof is intuitive. $$$\text{popcount}(x\ \&\ y)$$$ should be even according to Lemma 2, where $$$x$$$ is any of bases in $$$A$$$ and $$$y$$$ is any of bases in $$$B$$$. Since we've divided key bits for two linear basis, $$$\text{popcount}(x\ \&\ y)$$$ is not more than $$$2$$$. Once two symmetrical non-key bits are $$$0$$$, $$$1$$$ respectively, there will exist $$$x$$$, $$$y$$$ satisfying $$$\text{popcount}(x\ \&\ y) = 1$$$. Otherwise, $$$\text{popcount}(x\ \&\ y)$$$ is always $$$0$$$ or $$$2$$$.
In order to get $$$B$$$, you can also divide $$$A$$$ into $$$k$$$ small linear basis, construct their orthogonal linear basis and intersect them. It is harder to implement.
Lemma 5: The $$$i$$$-th number of $$$\text{FWT}(F^c)$$$ only depends on $$$\text{popcount}(i)$$$.
Proof: The $$$i$$$-th number of $$$F^c$$$ only depends on $$$\text{popcount}(i)$$$, so it still holds after Fast Walsh-Hadamard Transform.
Let $$$w_d^c$$$ be the $$$(2^d-1)$$$-th number of $$$\text{FWT}(F^c)$$$. Again, Fast Walsh-Hadamard Transform tells us:
• $$$w_d^c = \sum\limits_{i=0}^{2^m-1} [\text{popcount}(i)=c](-1)^{\text{popcount}(i\ \&\ (2^d-1))}$$$
Note that $$$\text{popcount}(2^d-1)=d$$$. Let's enumerate $$$j = \text{popcount}(i\ \&\ (2^d-1))$$$. There are $$$\dbinom{d}{j}$$$ different intersections, each one has $$$\dbinom{m-d}{c-j}$$$ ways to generate the remaining part of $$$i$$$. So:
• $$$w_d^c = \sum\limits_{j=0}^{d} (-1)^j \dbinom{d}{j}\dbinom{m-d}{c-j}$$$
It takes $$$O(m^3)$$$ to calculate all necessary combinatorial numbers and $$$w_d^c$$$.
Finally, let's consider the sum of every number in $$$\text{FWT}(A) * \text{FWT}(F^c)$$$. Suppose $$$q_i$$$ is equal to the number of $$$x$$$, where $$$x \in S(B)$$$ and $$$\text{popcount}(x)=i$$$. We can easily get:
• $$$p_c = \dfrac{1}{2^m}\sum\limits_{d=0}^{m} 2^k q_d w_d^c = \dfrac{1}{2^{m-k}}\sum\limits_{d=0}^{m} q_d w_d^c$$$
Just like Algorithm 1. We can enumerate each base of $$$B$$$ is picked or not, find out the whole $$$S(B)$$$ in $$$O(2^{m-k})$$$, get $$$q_0 \ldots q_m$$$ and calculate $$$p_0 \ldots p_m$$$ at last. Since one of $$$A$$$, $$$B$$$ has a length of not more than $$$m/2$$$, we just need to enumerate bases of the smaller one in order to pass the hard version in $$$O(2^{m/2} + m^3 + n)$$$.