#1531. 「EC Final 2019」狄利克雷 k 次根 加强版

「EC Final 2019」狄利克雷 k 次根 加强版

题目描述

题面参考 Codeforces Gym 102471 C. Dirichlet kk-th root

请注意,唯一的不同为数据范围。

定义两个函数 f,g:{1,2,,n}Zf, g: \{1, 2, \dots, n\} \rightarrow \mathbb Z 的狄利克雷卷积 fgf * g 为:

(fg)(n)=dnf(d)g(nd)(f * g)(n) = \sum_{d | n} f(d)g(\frac nd)

我们定义 g=fkg = f^kkk 次幂为:

$$f^{k}=\underbrace {f * \dots * f} _{k~{\textrm {个}}} $$

在本题中,我们想要解决这个问题的逆问题:给你 ggkk,你需要找到一个函数 ff 使得 g=fkg = f^k

另外,保证 g(1)=1g(1)=1,你需要保证 f(1)=1f(1)=1。所有的运算在 Fp\mathbb F_p 上进行,其中 p=998244353p = 998244353,这意味着狄利克雷卷积为 $(f*g)(n) = \left(\sum_{d|n} f(d)g(\frac nd)\right) \bmod p$。

输入格式

第一行输入两个正整数 n,kn, k

第二行输入 nn 个整数,g(1),g(2),,g(n)g(1), g(2), \dots, g(n),保证 0g(i)<998244353,g(1)=10\le g(i) < 998244353, g(1) = 1

输出格式

如果无解,输出 1-1

否则,一行输出 nn 个整数 f(1),f(2),,f(n)f(1), f(2), \dots, f(n),要求 0f(i)<998244353,f(1)=10\le f(i) < 998244353, f(1)=1,如果有多个解,你只需要输出任意一个。

样例

5 2
1 8 4 26 6
1 4 2 5 3

数据范围与提示

对于 50%50\% 的数据,保证 n105n\le 10^5

对于 100%100\% 的数据,保证 2n106,1k<9982443532\le n\le 10^6, 1\le k < 998244353