#P5245. 【模板】多项式快速幂

【模板】多项式快速幂

题目背景

加强版传送门

模板题,无背景

题目描述

给定一个 n1n-1 次多项式 A(x)A(x),求一个在 mod xn\bmod\ x^n 意义下的多项式 B(x)B(x),使得 B(x)(A(x))k (mod xn)B(x) \equiv (A(x))^k \ (\bmod\ x^n)

多项式的系数在 mod 998244353\bmod\ 998244353 的意义下进行运算。

输入格式

第一行两个整数 n,kn,k

接下来 nn 个整数,依次表示 A(x)A(x) 的系数 a0,a1,...,an1a_0, a_1,...,a_{n-1}

输出格式

输出 nn 个整数,依次表示 B(x)B(x) 的前 nn 项系数 b0,b1,...,bn1b_0, b_1,...,b_{n-1} 在模 998244353998244353 意义下的最小自然数值。

9 18948465
1 2 3 4 5 6 7 8 9
1 37896930 597086012 720637306 161940419 360472177 560327751 446560856 524295016
4 1
1 1 0 0

1 1 0 0
4 2
1 1 0 0

1 2 1 0

4 3
1 1 0 0
1 3 3 1

提示

对于 100%100\% 的数据,1<n1051 < n \leq 10^50<k101050 < k \leq 10^{10^5}ai[0,998244352]a_i \in [0,998244352]a0=1a_0=1