問題一覧 > 通常問題

No.3619 Compositional Power with Schröder Coordinate

レベル : / AI推定難易度 : 2700 / 実行時間制限 : 1ケース 10.000秒 / メモリ制限 : 1024 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 20
作問者 : noya2 / テスター : lif4635
お気に入りにしたユーザー ProblemId : 13839 / 自分の提出
問題文最終更新日: 2026-08-10 20:09:21
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 508 (順位表) の他の問題:

Note

The time limit for this problem is $10$ seconds.

Problem Statement

You are given integers $n,m$. It is guaranteed by the constraints 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]]$. It is guaranteed by the constraints 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}}$

Find $f^{\langle m\rangle}(x)\bmod x^n = \sum_{i=0}^{n-1}\mathrm{ans}_i x^i$. Here, $f^{\langle m\rangle}(x)$ denotes the $m$-fold composition of $f(x)$.

Constraints

  • All inputs are integers.
  • $3\le n\le 200000$
  • $1\le m\le 10^9$
  • $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}_{n-1}$

Sample

Sample 1
Input
4 2
0 2 0 1
0 1 0 831870294
0 1 0 166374059
Output
0 4 0 10
Sample 2
Input
10 1000000000
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 851104391 401777859 691006525 444992555 559055363 329863477 85844850 547301501 52035613

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。