P10106 [GDKOI2023 Senior] You Are the Busiest in the Circus.

You are performing a show in a circus. There is a number with initial value $x_0$. Perform $K$ operations. In the $i$-th operation, pick a number $x$ uniformly at random from $[0, 2^n)$. With probability $p$, $x_i = x_{i - 1} \operatorname{or} x$; with probability $1 - p$, $x_i = x_{i - 1} \operatorname{and} x$. The weight of one plan is $\sum_{i=1}^K c_{x_i}$. For each $i \in [0, 2^n)$, compute, among all plans with $x_K = i$, the sum of (weight $\times$ probability), taken modulo $998244353$.

The first line contains four integers $n, p', K, x_0$. Here $p'$ is the value of $p$ modulo $998244353$. The second line contains $2^n$ integers. The $i$-th integer denotes $c_{i - 1}$.

Output one line with $2^n$ integers separated by spaces. The $i$-th integer denotes, among all plans with $x_K = i - 1$, the sum of (weight $\times$ probability), taken modulo $998244353$.

For $20\%$ of the testdata, $K \le 20$. For $40\%$ of the testdata, $K \le 10^3$. For another $10\%$ of the testdata, $n = 1$. For another $10\%$ of the testdata, $n \le 8$. For another $10\%$ of the testdata, $p' = 499122177$. For another $10\%$ of the testdata, $c_i = 1$. For $100\%$ of the testdata, $0 \le n \le 17$, $1 \le K \le 10^9$, $0 \le x_0 < 2^n$, $0 \le p', c_i < 998244353$. Translated by ChatGPT 5