下降幂多项式的运算
下降幂多项式的运算
下降幂的定义
下降幂 \(\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}\) 为 \(\displaystyle EGF(F(x))=\sum_0^{\infty}\frac{F(i)x^i }{i!}\)。 \[ \begin{aligned} EGF(F(x))&=\sum_{i=0}^{\infty}\frac{x^i}{i!}\sum_{j=0}^{n} \frac{i!}{(i-j)!}\cdot F_j \\ &=\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 \\ &=\sum_{i=0}^{n} F_i \cdot x^i \sum_{j=0}^{\infty}\frac{1}{j!} x^j \\ &=\sum_{i=0}^{n} F_i \cdot x^i e^x \end{aligned} \]
那么直接和 \(e^x\) 卷积就可以得到 \(F(x)\) 的 \(\text{EGF}\)。
Tips: \(e^x\) 直接带入展开式 \(\displaystyle e^{ax}=\sum_0^{\infty}\frac{(ax)^i}{i!}\)。
如果要从 \(\text{EGF}\) 得到 \(F(x)\)。
\(\displaystyle EGF(F(x))=\sum_{i=0}^{n} F_i \cdot x^ie^x\)
\(\displaystyle F_i=\frac{EGF(F(x))}{x^ie^x}\)
那么就直接卷上 \(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)\)，奇数项系数取反。