No.3620 Compositional Power with Schröder Coordinate 2
Note
The execution time limit for this problem is $10$ seconds.
Problem Statement
You are given integers $n,m$. Here, the constraints guarantee that $n\ge 3$.
You are given formal power series $f(x)\coloneqq \sum_{i=0}^{n-1}a_i x^i\in \mathbb{F}_{998244353}[[x]], g(x)\coloneqq \sum_{i=0}^{n-1}b_i x^i \in\mathbb{F}_{998244353}[[x]], h(x)\coloneqq \sum_{i=0}^{n-1}c_i x^i \in\mathbb{F}_{998244353}[[x]]$. The constraints guarantee that they satisfy the following properties.
- $a_0=0$
- $a_1^i \not\equiv a_1 \pmod {998244353}\ (i=2,3,\dots, n-1)$
- $b_0=0$
- $b_1=1$
- $g(f(x)) \equiv a_1 g(x)\pmod {x^{n}}$
- $g(h(x)) \equiv h(g(x)) \equiv x\pmod {x^{n}}$
For $k=0,1,\dots, m-1$, find $\mathrm{ans}_k=[x^{n-1}]f^{\langle k\rangle}(x)$. Here, $f^{\langle k\rangle}(x)$ denotes the $k$-fold composition of $f(x)$. Note that $f^{\langle 0\rangle}(x)=x$.
Constraints
- All inputs are integers.
- $3\le n\le 200000$
- $1\le m\le 200000$
- $0\le a_i,b_i,c_i\lt 998244353$
- $a_0=0$
- $a_1^i \not\equiv a_1 \pmod {998244353}\ (i=2,3,\dots, n-1)$
- $b_0=0$
- $b_1=1$
- $f(x),g(x)$ defined in the problem statement satisfy $g(f(x)) \equiv a_1 g(x)\pmod {x^{n}}$.
- $g(x),h(x)$ defined in the problem statement satisfy $g(h(x)) \equiv h(g(x)) \equiv x\pmod {x^{n}}$.
Input
$n$ $m$
$a_0$ $a_1$ $\dots$ $a_{n-1}$
$b_0$ $b_1$ $\dots$ $b_{n-1}$
$c_0$ $c_1$ $\dots$ $c_{n-1}$
Output
Output in the following format. Here, $\mathrm{ans}_i$ must be an integer satisfying $0\le \mathrm{ans}_i\lt 998244353$.
$\mathrm{ans}_0$ $\mathrm{ans}_1$ $\dots$ $\mathrm{ans}_{m-1}$
Sample
Sample 1
Input
4 5 0 2 0 1 0 1 0 831870294 0 1 0 166374059
Output
0 1 10 84 680
Sample 2
Input
10 10 0 2 97460621 111410723 910781021 787650035 525397272 778634186 769261814 17908181 0 1 450391866 851628676 116766808 102424189 629373870 830133384 438172635 610210161 0 1 547852487 703228107 427427877 24030916 160333921 387872980 756810038 143082494
Output
0 17908181 843221153 4917907 82933009 322242863 739542286 396333110 593115987 280837161
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。
noya2