#P5265. 多项式反三角函数

    ID: 4204 远端评测题 1000ms 125MiB 尝试: 0 已通过: 0 难度: 7 上传者: 标签>倍增O2优化构造快速数论变换 NTT

多项式反三角函数

题目描述

给定一个 n1n-1 次多项式 A(x)A(x),求一个 modxn\bmod{\:x^n} 下的多项式 F(x)F(x),满足 F(x)asinA(x)F(x)\equiv\text{asin}\:A(x)F(x)atanA(x)F(x)\equiv\text{atan}\:A(x)

所有运算在 mod 998244353\bmod\ 998244353 意义下进行。

输入格式

第一行 两个 整数 n,typen,type,若 type=0type=0 代表求 asin\text{asin},若 type=1type=1 代表求 atan\text{atan}

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

保证 a0=0a_0=0

输出格式

输出一行 nn 个整数,表示答案多项式中的系数 f0,f1,,fn1f_0,f_1,\cdots,f_{n-1}

8 0
0 4 2 6 1 5 3 7
0 4 2 665496252 17 399297879 332748370 570426983
8 1
0 4 2 6 1 5 3 7
0 4 2 665496220 998244322 399297839 332748518 570424795

提示

对于 100%100\% 的数据:n105n\leq10^5ai[0,998244352]Za_i\in[0,998244352]\cap\mathbb{Z}

55 个点 type=0type=0,后 55 个点 type=1type=1