Bitwise Magic
Contest: Grakn Forces 2020
Difficulty rating: 3200
Tags: dp, math

You are given a positive integer $$$k$$$ and an array $$$a_1, a_2, \ldots, a_n$$$ of non-negative distinct integers not smaller than $$$k$$$ and not greater than $$$2^c-1$$$.

In each of the next $$$k$$$ seconds, one element is chosen randomly equiprobably out of all $$$n$$$ elements and decreased by $$$1$$$.

For each integer $$$x$$$, $$$0 \leq x \leq 2^c - 1$$$, you need to find the probability that in the end the bitwise XOR of all elements of the array is equal to $$$x$$$.

Each of these values can be represented as an irreducible fraction $$$\frac{p}{q}$$$, and you need to find the value of $$$p \cdot q^{-1}$$$ modulo $$$998\,244\,353$$$.

Input format:
The first line of input contains three integers $$$n, k, c$$$ ($$$1 \leq n \leq (2^c - k)$$$, $$$1 \leq k \leq 16$$$, $$$1 \leq c \leq 16$$$).

The second line contains $$$n$$$ distinct integers $$$a_1, a_2, \ldots, a_n$$$ ($$$k \leq a_i \leq 2^c-1$$$).

Output format:
Print $$$2^c$$$ integers: the probability that the bitwise XOR is equal to $$$x$$$ in the end for $$$x$$$ in $$$\{0, 1, \ldots, 2^c-1\}$$$ modulo $$$998\,244\,353$$$.

Constraints:
Time limit: 6.0 s
Memory limit: 256.0 MB

Example input:
4 1 3
1 2 3 4

Example output:
0 0 0 748683265 0 499122177 0 748683265

Editorial:
There are several solutions to this problem, with various complexities. Some of our solutions work in less than half a second. The constraints were set to allow most non-naive solutions.
Solution 1, DP on Trie
Let's look at the bitwise trie. Each node corresponds to some segment $$$[l, r]$$$ of possible numbers. Let's note that if you perform operations on numbers in $$$[l + k, \ldots, r]$$$, then the resulting numbers for them won't leave the trie node.
So we can come up with the following solution: let's maintain some kind of a DP on this trie. When we took into account numbers from $$$a$$$ among $$$[l + k, \ldots, r]$$$, and we should store the FWHT for each number of operations (we can assume that we store some kind of an exponential generating functions for each value in FHWT and maintain the product of those genfuncs for numbers with the corresponding signs). Note that in this FWHT you are interested only in $$$O(r - l)$$$ values (because all given numbers have equal prefixes, so if you know the parity of the number, you know the prefix of the total XOR).
To recalculate this DP, when we calculated it for children, at first in $$$O((r - l)k^2)$$$ you should multiply DP's for the children, and then you should add first $$$k$$$ numbers of the right subtree (that you didn't consider yet) to this DP, you can do it for each of them in $$$O((r - l)k^2)$$$.
If some details are not clear for you here, probably you are not familiar with FWHT enough.
Deriving the total complexity of $$$2^c \cdot c \cdot k^3$$$.
Of course, a lot of different further optimizations possible for this solution.
Solution 2, Observations
The main observation: the number of different tuples $$$x \oplus x, x \oplus (x-1), x \oplus (x-2), \ldots, x \oplus (x - k)$$$ is around $$$O(kc)$$$.
Why? Because consider how $$$x$$$ is changed during the process, usually only $$$O(\log k)$$$ bits are changed, but once one block of zeroes of the length $$$O(\log n)$$$ is changed to ones. So if we know the last $$$O(\log k)$$$ bits of the number and the length of the block of zeroes after them, we can identify s $$$x \oplus x, x \oplus (x-1), x \oplus (x-2), \ldots, x \oplus (x - k)$$$.
If you notice this, you can note a lot of other similar observations, and derive another solution with better complexity than naive. And then using DP/FWHT, you can upgrade those ideas to the solution.
For example, QAQautomaton wrote the solution in $$$2^c \cdot c^2 + c^6$$$ using this idea.
I will leave all remaining details as an exercise for the reader.