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

内存限制:256 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: EntropyIncreaser

题目描述

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

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

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

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

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

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

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

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

输入格式

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

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

输出格式

如果无解,输出 -1

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

样例

样例输入 1

5 2
1 8 4 26 6

样例输出 1

1 4 2 5 3

数据范围与提示

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

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