Create your team from https://mirror.codeforces.com/teams then register and choose team participation.

Personally, it's your name

I'll write this assuming you know how Walsh-Hadamard transform works. If you don't want to, you can use this definition to connect the dots: $$$\displaystyle B_i=\sum_{j=0}^{2^d-1}(-1)^{\texttt{popcount}(i \texttt{&} j)} A_j$$$. Here $$$B$$$ is the forward transform of $$$A$$$, $$$d$$$ is the maximum number of bits, and that's bitwise and in the exponent. The inverse transform is the same, except that we divide everything by $$$2^d$$$ in the end.

Note that the answer is the constant term of $$$P(x)=\displaystyle\prod_{i=1}^N \left(1+2x^{a_i}\right)$$$ where we define $$$x^i\cdot x^j = x^{i\oplus j}$$$ (bitwise xor). Consider the Walsh-Hadamard transform of $$$1+2x^{a_i}$$$ for some $$$i$$$. The resulting coefficients only take the values $$$1\pm 2$$$. The transform of $$$P(x)$$$ is the elementwise product of the transforms of the $$$1+2x^{a_i}$$$ terms. So you only need to count for each $$$0\leq k < 2^d$$$ the number of $$$1+2x^{a_i}$$$ terms that take each of the coefficients $$$1\pm 2$$$ at the $$$k$$$-th position. This is equivalent to computing the number of $$$a_i$$$ values that have an even/odd number of bits in common with $$$k$$$. Then the corresponding coefficient at $$$k$$$-th position would be something like $$$(-1)^{\texttt{#odd}} 3^{\texttt{#even}}$$$. There are (at least) two ways to do this fast.

You can do something similar to SOS DP. Define $$$f[i][S][p]$$$ to be the count of numbers in the array with the following property: the parity of their intersection (bitwise and) with the first $$$i$$$ bits of $$$S$$$ is $$$p$$$, while the rest of the bits match $$$S$$$. The transitions are simple, you consider both options for the $$$i$$$-th bit. This was my solution, which doesn't require you to directly apply FWHT.

Or, you can notice that the Walsh-Hadamard transform of $$$\displaystyle Q(x)=\sum_{i=0}^{2^d-1} c_i x^i$$$ gives us almost the quantity we want, where $$$c_i$$$ is the count of the number $$$i$$$ in the array. The $$$k$$$-th coefficient in the forward transform gives us the value of $$$\texttt{#even}-\texttt{#odd}$$$. Together with the fact that $$$\texttt{#even}+\texttt{#odd}=N$$$, you can derive the required values. I noticed it after a discussion with YouKn0wWho, who solved it this way (and according to whom, a similar problem has appeared somewhere before).

Both of these approaches lead to an $$$\mathcal O\left (2^d d\right)$$$ solution. One final remark is that you don't need the inverse transform, as the sum of coefficients in the forward transform is the original constant term, times $$$2^d$$$.

TBH, there was an exact same problem in China a few years ago, and various solutions were introduced in the solution.

I'll be honest, we are using MS PowerPoint :)

Observe firstly that any newly added node must be a descendant of a node in the $$$L$$$th level or ($$$L-1$$$)th level of the formed bfs tree till now (here $$$L$$$ is the max level of any leaf).

Imagine building the tree of the array elements from left to right. Let $$$dp(x,y)$$$ denote the number of valid trees formed from the first $$$x$$$ numbers of the array and in which there are $$$y$$$ nodes "eligible" to be a parent of the new node. So they must be some $$$f_1,f_2,....,f_m,g_1,g_2,...,g_{y-m}$$$ where $$$f_i$$$ are in the second last level and $$$g_i$$$ are in the last level (according to the in-order traversal). Clearly here $$$g_{y-m}$$$ is the $$$x$$$th element of the array and $$$f_1$$$ is its parent. So if $$$a[x+1] > a[x]$$$, then you can make $$$f_1$$$ as parent of $$$x+1$$$, but if $$$a[x+1]<a[x]$$$ you can't. Moreover if you choose the $$$k$$$th node of the eligible parents as the parent of $$$x+1$$$, the previous $$$k-1$$$ nodes are no more eligible, and for $$$a$$$ to be a valid BFS, the only extra edges that can be made to $$$x$$$th node are with the $$$y-k$$$ eligible parents ahead of its current parent. Thus for $$$a[x+1]>a[x]$$$ you add $$$2^{z-2}dp(x,y)$$$ to $$$dp(x+1,z)$$$ for $$$1\leq z\leq y+1$$$ and for $$$a[x+1]<a[x]$$$, you add $$$2^{z-2}dp(x,y)$$$ to $$$dp(x+1,z)$$$ for $$$1\leq z\leq y$$$. (note that the newly added node would become an eligible parent for further dp). Thus by maintaining prefixes you can solve the problem in $$$O(n^2)$$$.

You can find the PDF version of the problems from the ICPC 2023 Jakarta GitHub repository. However, the combined problemset PDF is not available, so you might need to print it one by one.