P10249 [Template] Polynomial Composition Function (Enhanced Version)

Compared with [P5373](https://www.luogu.com.cn/problem/P5373), this problem has larger constraints.

Given an $n$-degree polynomial $F(x)$ and an $m$-degree polynomial $G(x)$, you need to find an $n$-degree polynomial $H(x)$ that satisfies: $$H(x) \equiv F(G(x))\space (\text{mod }x^{n+1})$$ In other words, the polynomial you need should satisfy: $$H(x) \equiv \sum_{i=0}^n [x^i]F(x)\times G(x)^i \space (\text{mod }x^{n+1})$$ Take all coefficients of the result modulo $998244353$.

The first line contains two positive integers $n,m$, which are the degrees of $F(x)$ and $G(x)$, respectively. The second line contains $n+1$ non-negative integers $f_i$, where $f_i$ is the coefficient of the $i$-th power term of $F(x)$. The third line contains $m+1$ non-negative integers $g_i$, where $g_i$ is the coefficient of the $i$-th power term of $G(x)$.

Output one line with $n+1$ non-negative integers, representing the coefficients of $H(x)$ from low degree to high degree.

**Constraints:** - $1\le m \le n \le 200000$ - $f_i,g_i \in [0,998244353)\cap \mathbb Z$ | Test Point ID | $m,n\le$ | | :----------: | :----------: | | $1,2$ | $30000$ | | $3,4$ | $50000$ | | $5,6$ | $100000$ | | $7,8$ | $150000$ | | $9,10$ | $200000$ | Translated by ChatGPT 5