下降幂多项式
下降幂多项式
下降幂的定义
下降幂$\text{Falling Factorial}$
下降幂多项式$\text{Falling Factorial Polynomial}$下面简称$\text{FFP}$
$x$的$n$阶下降幂$x^{\underline n}=\prod_0^{n-1}(x-i) = \frac{x!} {(x-n)!}$
一个下降幂多项式$F(x)=\sum a_ix^{\underline i}$
快速求解$x^{\underline n}$的展开形式
$x^{\underline{n} }=x(x-1)\cdots (x-n+1)$
考虑倍增求解，假设已知$F(x)=x^{\underline{n} }$
要求$G(x)=x^{\underline{2n} }$
显然$G(x)=F(x)F(x-n)$
而$\begin{aligned} F(x-n)=\sum_{i=0}^{n} [x^i]F(x) \cdot (x-n)^i\end{aligned}$
用一次卷积处理这个二项展开即可
复杂度为$O(n\log n)$
FFP与其点值的$\text{EGF}$
点值的$\text{EGF}$为$\begin{aligned} EGF(F(x))=\sum_0^{\infty}\frac{F(i)x^i } {i!}\end{aligned}$
$\begin{aligned}EGF(F(x))=\sum_{i=0}^{\infty}\frac{x^i} {i!}\sum_{j=0}^{n} \frac{i!} {(i-j)!}\cdot F_j\end{aligned}$ $\begin{aligned}EGF(F(x))=\sum_{i=0}^{\infty}x^i \sum_{j=0}^{n} \frac{1} {(i-j)!}\cdot F_j\end{aligned}$换一下顺序
$\begin{aligned}EGF(F(x))=\sum_{i=0}^{n} F_i \sum_{j=i}^{\infty}\frac{1} {(j-i)!} x^j\end{aligned}$ $\begin{aligned}EGF(F(x))=\sum_{i=0}^{n} F_i \cdot x^i \sum_{j=0}^{\infty}\frac{1} {j!} x^j\end{aligned}$ $\begin{aligned}EGF(F(x))=\sum_{i=0}^{n} F_i \cdot x^i e^x\end{aligned}$那么直接和$e^x$卷积就可以得到$F(x)$的$\text{EGF}$
Tips: $e^x$直接带入展开式$\begin{aligned} e^{ax}=\sum_0^{\infty}\frac{(ax)^i} {i!} \end {aligned}$
如果要从$\text{EGF}$得到$F(x)$
$\begin{aligned}EGF(F(x))=\sum_{i=0}^{n} F_i \cdot x^ie^x\end{aligned}$ $\begin{aligned} F_i=\frac{EGF(F(x))} {x^ie^x} \end{aligned}$那么就直接卷上$e^{-x}$就可以了
即可以通过简单卷积完成$\text{FFP} \Longleftrightarrow \text{EGF}$的转化
FFP卷积
求出$\text{EGF}$，然后点值对应相乘(注意乘完之后要补上一个$i!$)，最后再反求$F(x)$
Tips: 下面的知识恐怕需要先学多点求值/快速插值
多项式转FFP
带入$0,\cdots n-1$，多点求值得到$\text{FFP}$点值的$EGF$，然后求得到$\text{FFP}$
FFP转多项式
求出$F(x)$的$EGF$，然后带入前$n$项的值，快速插值回来即可
由于$x_i$是连续的，所以不需要再多点求值求解$\prod\frac{1} {x_i-x_j}$，可以直接阶乘得到
关于上升幂
$x^{\overline n}=\frac{(x+n-1)!} {(x-1)!}=x(x+1)(x+2)\cdots(x+n-1)$
容易发现的是$x^{\overline n}=(-x)(-((-x)-1))(-((-x)-2))\cdots (-(-x-(n-1)))=(-1)^n (-x)^{\underline{n} }$
所以上升幂多项式与普通多项式的转化 可以认为是上面的点值变成了$0,-1,\cdots ,-(n-1)$，奇数项系数取反