题目背景
模板题,无背景。
题目描述
给定一个 n 次下降幂多项式 A(x) 和 m 次下降幂多项式 B(x),你要求出一个 n+m 次下降幂多项式 F(x) 满足 F(x)=A(x)B(x)。
由于结果会很大,你输出的多项式的系数应对 998244353 取模。
输入格式
第一行两个正整数 n,m,表示下降幂多项式的次数。
第二行 n+1 个非负整数 a0,a1,a2,…,an,表示 A(x) 的系数。即 A(x)=a0+a1x+a2x2+⋯+anxn。
第三行m+1个非负整数b0,b1,b2,…,bm,表示 B(x) 的系数。即 B(x)=b0+b1x+b2x2+⋯+bmxm。
输出格式
一行,共 n+m+1 个非负整数,表示 F(x) 的各项系数对 998244353 取模后的结果。
提示
对于 20%的数据,n,m⩽1000。
对于 100% 的数据,1⩽n,m⩽105,ai,bi∈[0,998244353),an,bm=0。
提示
xn={1x×(x−1)n−1n=0n⩾1
i=0∑naixi,an=0 是 x 的 n 次下降幂多项式。
容易证明 n 次下降幂多项式唯一确定一个 n 次多项式,所以下降幂多项式乘积的定义就是对应的多项式的乘积对应的下降幂多项式。