31294번 - Convolution 스페셜 저지다국어

Consider all subsets of set $U = \{0, 1, 2, \dots, n-1\}$. Every subset $A = \{a_1, a_2, \dots, a_k\}$ corresponds to a unique integer $p(A) = \sum\limits_{i=1}^k 2^{a_i}$. Let function $F$ of an $n$-element set be defined by an array of integers $f$ of length $2^n$: the value $F(A)$ is equal to $f[p(A)]$.

You are given two functions $F$ and $G$. Your task is to find such function $H$ that $$H(A) = \sum\limits_{B \cup C = A}F(B)G(C)\text{.}$$

The first line contains two integers $n$ and $t$ ($1 \le n \le 16$, $1 \le t \le 100$). Here, $n$ is the size of the set $U$, and $t$ is number of test cases. The second line contains two integers $a$ and $b$, each from $1$ to $10^9$. These numbers are used in the following pseudo-random generator:

1. unsigned int cur = 0; // unsigned 32-bit integer
2. unsigned int nextRand16() {
3.   cur = cur * a + b; // calculated modulo 232
4.   return cur / 216; // integer from 0 to 216-1
5. }

The test cases are generated successively. In each of them, first, you must generate the elements of array $f$ (values of $F$) in the order of increasing array index, and after that, you must generate the elements of $g$ (values of $G$) in the same order. Each element is generated by calling the function nextRand16().

For each test case, print one integer on a separate line: $\left(\sum\limits_A H(A) \cdot (p(A)+1)\right) \bmod 2^{32}\text{.}$

The arrays in the first example are the following:

• $f_1 \colon 3,113,3395,36331,41370,61471,9130,11774$
• $g_1 \colon 25547,45526,55066,13590,14501,41817,9356,18543$
• $h_1 \colon 76641,8167827,273846333,5284992017,1656829263,11450721456,3699971823,14260048942$
• $f_2 \colon 32024,43238,51978,52034,53714,38578,43250,52338$
• $g_2 \colon 62834,50034,59250,8050,44914,36722,53106,20338$
• $h_2 \colon 2012196016,6482475400,8243104152,15561662464,7225902008,16869349792,22350138288,44342816072$