#P3711. 仓鼠的数学题

    ID: 4464 远端评测题 1000ms 125MiB 尝试: 0 已通过: 0 难度: 7 上传者: 标签>洛谷原创O2优化生成函数逆元洛谷月赛

仓鼠的数学题

题目背景

请注意本题时限 1s,开启 O2 优化,你可能需要输入输出优化。

题目描述

仓鼠在某 oj 上看到了一个问题,设 Sk(x)=i=0xikS_k(x)=\sum_{i=0}^x i^k,这个题输入 a0,a1...ana_0,a_1...a_n,假设 00=10^0=1,要求计算 k=0nSk(x)ak\sum_{k=0}^{n}S_k(x)a_k

仓鼠想了两秒就秒了这个题,他发现数据范围居然只有 10001000,就顺手加了两个 00

但是仓鼠懒得造数据了,就把这道题丢给了你。

输入格式

第一行输入一个整数 nn

第一行输入 n+1n+1 个空格分隔的非负整数。分别是 a0,,ana_0, \cdots, a_n

输出格式

输出 n+2n+2 个空格分隔的整数,表示答案多项式的各项系数 c0,,cn+1c_0,\cdots,c_{n+1},表示答案多项式为 i=0n+1cixi\sum_{i=0}^{n+1}c_ix^i。多项式的系数对 998244353998244353 取模。

可以证明多项式的次数 n+1\leq n+1

2
3 3 3
3 5 3 1

提示

对于 10%10\% 的数据,n500n \leq 500

对于 30%30\% 的数据,n3000n \leq 3000

对于 70%70\% 的数据,n100000n \leq 100000

对于 100%100\% 的数据,1n2500001 \leq n \leq 250000

输入和输出多项式系数均为模 998244353998244353 意义下,为 [0,998244352][0,998244352] 的非负整数。