P5394 【模板】下降幂多项式乘法
题目背景
模板题,无背景。
题目描述
给定一个 $n$ 次下降幂多项式 $A(x)$ 和 $m$ 次下降幂多项式 $B(x)$,你要求出一个 $n+m$ 次下降幂多项式 $F(x)$ 满足 $F(x)=A(x)B(x)$。
由于结果会很大,你输出的多项式的系数应对 $998244353$ 取模。
输入格式
无
输出格式
无
说明/提示
对于 $20\%$的数据,$n,m\leqslant 1000$。
对于 $100\%$ 的数据,$1\leqslant n,m\leqslant 10^5$,$a_i,b_i\in[0,998244353)$,$a_n,b_m \neq 0$。
## 提示
$x^{\underline n}=\left\{\begin{matrix}1 & n=0\\ x\times (x-1)^{\underline{n-1}} & n\geqslant 1 \end{matrix}\right.$
$\sum\limits_{i=0}^n a_ix^{\underline i},a_n\neq 0$ 是 $x$ 的 $n$ 次下降幂多项式。
容易证明 $n$ 次下降幂多项式唯一确定一个 $n$ 次多项式,所以下降幂多项式乘积的定义就是对应的多项式的乘积对应的下降幂多项式。