#P4238. 【模板】多项式乘法逆

    ID: 4908 远端评测题 1000ms 125MiB 尝试: 0 已通过: 0 难度: (无) 上传者: 标签>数学递推倍增递归逆元快速傅里叶变换 FFT

【模板】多项式乘法逆

题目背景

注意:本题并不属于中国计算机学会划定的提高组知识点考察范围。

题目描述

给定一个多项式 F(x)F(x) ,请求出一个多项式 G(x)G(x), 满足 F(x)G(x)1(modxn)F(x) * G(x) \equiv 1 \pmod{x^n}。系数对 998244353998244353 取模。

输入格式

首先输入一个整数 nn, 表示输入多项式的项数。
接着输入 nn 个整数,第 ii 个整数 aia_i 代表 F(x)F(x) 次数为 i1i-1 的项的系数。

输出格式

输出 nn 个数字,第 ii 个整数 bib_i 代表 G(x)G(x) 次数为 i1i-1 的项的系数。保证有解。

5
1 6 3 4 9
1 998244347 33 998244169 1020

提示

对于 100%100\% 的数据,1n1051 \leq n \leq 10^50ai109 0 \leq a_i \leq 10^9