P16916 [JLCPC 2026] Counting Trees

You are given an integer $K$, and two arrays $a_1, a_2, \ldots, a_{2^K - 1}$ and $b_1, b_2, \ldots, b_{2^K - 1}$, each of length $2^K - 1$. There is an undirected complete graph $G$ with $2^K$ vertices, labeled from $0$ to $2^K - 1$. For a spanning tree $T$ of graph $G$, define $$ \begin{aligned} A(T) &= \prod_{(u,v)\in T} a_{u\oplus v},\\ B(T) &= \sum_{(u,v)\in T} b_{u\oplus v},\\ C(T) &= \bigoplus_{(u,v)\in T} (u\oplus v). \end{aligned} $$ For each $0 \le x < 2^K$, you need to compute $$ \left(\sum_{\substack{T\\ C(T)=x}} A(T)B(T)^p\right) \bmod 998244353, $$ where $p$ is a given constant. It is defined that $0^0=1$. > An undirected complete graph means there is an undirected edge between every pair of distinct vertices. A spanning tree means choosing some edges so that all vertices are connected and there is no cycle. The symbol $\oplus$ denotes bitwise XOR.

The first line contains two integers $K, p$ ($1 \le K \le 16$, $0 \le p \le 5$). The next line contains $2^K - 1$ integers; the $i$-th integer denotes $a_i$ ($0 \le a_i < 998244353$). The next line contains $2^K - 1$ integers; the $i$-th integer denotes $b_i$ ($0 \le b_i < 998244353$).

Output one line containing $2^K$ integers; the $i$-th integer is the answer for $x = i - 1$.

Translated by ChatGPT 5