11327: [yosupo] Set Power Series - Power Projection of Set Power Series
[Creator : ]
Description
Given an integer $M$, an $N$-variable polynomial $\displaystyle s(x _ 0, x _ 1, \dots, x _ {N - 1}) = \sum _ {i = 0} ^ {2 ^ N - 1} a _ i \prod _ {k = 0} ^ {N - 1} x _ k ^ {i _ k} \in \mathbb{F} _ {998244353} \lbrack x _ 0, x _ 1, \dots, x _ {N - 1} \rbrack$ and a sequence $(w _ 0, \ldots, w _ {2 ^ N - 1})$ of elements of $\mathbb{F} _ {998244353}$. Here, $i_k$ represents the number in the $2 ^ k$'s place when $i$ is expressed in binary.
For each $m=0,1,\ldots,M-1$, compute $\sum _ {i=0} ^ {2 ^ N - 1} w_ib_i$, where $b_i$ is defined by $s(x _ 0, x _ 1, \dots, x _ {N - 1})^m \equiv \sum _ {i = 0} ^ {2 ^ N - 1} b _ i \prod _ {k = 0} ^ {N - 1} x _ k ^ {i _ k} \pmod{(x _ 0 ^ 2, x _ 1 ^ 2, \dots, x _ {N - 1} ^ 2)}$.
For each $m=0,1,\ldots,M-1$, compute $\sum _ {i=0} ^ {2 ^ N - 1} w_ib_i$, where $b_i$ is defined by $s(x _ 0, x _ 1, \dots, x _ {N - 1})^m \equiv \sum _ {i = 0} ^ {2 ^ N - 1} b _ i \prod _ {k = 0} ^ {N - 1} x _ k ^ {i _ k} \pmod{(x _ 0 ^ 2, x _ 1 ^ 2, \dots, x _ {N - 1} ^ 2)}$.
Input
$N$ $M$
$a _ 0$ $a _ 1$ $\cdots$ $a _ {2^N-1}$
$w _ 0$ $w _ 1$ $\cdots$ $w _ {2^N-1}$
$a _ 0$ $a _ 1$ $\cdots$ $a _ {2^N-1}$
$w _ 0$ $w _ 1$ $\cdots$ $w _ {2^N-1}$
Output
$\mathrm{ans}_0$ $\mathrm{ans}_1$ $\cdots$ $\mathrm{ans}_{M-1}$
Constraints
- $0 \leq N \leq 20$
- $0 \leq M \leq 10^5$
- $0 \leq a_i, w_i \lt 998244353$
- $0 \leq M \leq 10^5$
- $0 \leq a_i, w_i \lt 998244353$
Sample 1 Input
2 10
1 2 3 4
5 6 7 8
Sample 1 Output
5 70 231 488 841 1290 1835 2476 3213 4046