#1592. 多项式求立方根

多项式求立方根

题目描述

这是一道 OJ 测试题。

给定 nn 次多项式 F(x)F(x),求 G(x)G(x) 满足 G3(x)F(x)(modxn+1)G^3(x)\equiv F(x) \pmod {x^{n+1}},也即,G(x)F(x)3(modxn+1)G(x)\equiv \sqrt[3]{F(x)}\pmod {x^{n+1}},保证常数项非零。

注意 F(x)3\sqrt[3]{F(x)} 在模 998244353998244353 下唯一。

所有运算在模 998244353998244353 下进行。

输入格式

第一行一个正整数 nn,意义见上。

第二行 n+1n+1 个正整数,表示 F(x)F(x)00 次项系数至 nn 次项系数。

输出格式

共一行,从低次项至高次项输出系数。

样例

7
1 9 2 6 0 8 1 7
1 3 665496227 43 221831826 665497874 419004875 813465047

数据范围与提示

保证 1n1051 \leq n \leq 10^5