AGC034 F - RNG and XOR

https://atcoder.jp/contests/agc034/tasks/agc034_f

Let a and b be arrays with 2^n elements. a*b denotes the xor convolution of a and b.

Let x=[x[0], x[1], ... , x[2^n-1]] be the answer and p=[p[0],...,p[2^n-1]] be the probability that i-th element is taken. The following relation holds.

\[ x \ast p = x + [2^{n}-1,-1,\ldots,-1]. \]

Let's consider the reason. The sum of x*p must be x[0]+...+x[2^n-1]. Thus, the first element of the right side must be 2^n-1.
H[x] denotes the hadamard transform of x. We then have

\[ H[x] \circ H[p] = H[x] + H[ [ 2^{n-1}-1,-1,\ldots,-1 ] ] \]

where a∘b denotes the bitwise product of arrays (also known as hadamard product.) Except i=0, we can figure out H[x][i]. For i=0, we cannot determine a value because H[p][0] = 1. Actually, we can assume that H[x][0] is any value. Once we determine H[x], we can obtain x by inverted hadamard transform. If H[x][0] is a wrong value, x[0],...,x[2^n-1] are also wrong. However, we can fix them because the answer is one of [x'[0], ... , x'[2^n-1]]=[x[0]+c, ... , x[2^n-1]+c]. We already know x'[0]=0, so c must be -x[0].