#P5277. 【模板】多项式开根(加强版)

    ID: 4204 远端评测题 1000ms 125MiB 尝试: 2 已通过: 1 难度: 6 上传者: 标签>快速傅里叶变换,FFT快速数论变换 NTT

【模板】多项式开根(加强版)

题目背景

模板题,无背景

题目描述

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

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

输入格式

第一行一个正整数nn

接下来nn个整数,依次表示多项式的系数a0,a1,,an1a_0,a_1,\cdots ,a_{n-1}

不保证a0=1a_0=1,但保证a0a_0mod 998244353\bmod\ 998244353下的二次剩余。

输出格式

输出 nn 个非负整数,表示答案多项式的系数b0,b1,bn1b_0,b_1\cdots ,b_{n-1}。如有多解,输出系数序列(而非字符序列)字典序最小的。

3
1 2 1
1 1 0
7
1 8596489 489489 4894 1564 489 35789489  
1 503420421 924499237 13354513 217017417 707895465 411020414

提示

对于25%25\%的数据,有n1000n \leq 1000

对于50%50\%的数据,有n104n \leq 10^4

对于75%75\%的数据,有n5×104n \leq 5\times 10^4

对于100%100\%的数据,有n105,ai[0,998244352]Zn \leq 10^5,a_i \in [0,998244352] \cap \mathbb{Z}