特殊多项式在整点上的线性插值方法

首先我来解释一下题目是什么东西,假如给你一个 k 次多项式 P(x),并且已知了 P(0), P(1), \cdots, P(k),要求计算出 P(n), n \in \mathbb N 的值,由于已经知道了 k + 1 个点值,那么要插值出系数是可以在 \mathcal O(k^2) 完成,如果使用 FFT 的话是可以在 \mathcal O(k \log^3 k) 的时间内完成的[1],但是对于这个特别的问题,我们有一个 \mathcal O(k) 的算法!这好像是杜教先提出来的,然后还有这篇文章

好了,现在来开始说要怎么做!首先明确一点,我们后面所说的 P(x)x 都认为是自然数

首先来看看组合数 {x \choose m},这个数是一个关于 xm 次多项式,因为它相当于是这样

 {x \choose m} = \frac{x(x - 1)(x - 2)\cdots (x - m + 1)}{m!}

并且 {x \choose 0}, {x \choose 1}, \cdots, {x \choose k} 的次数互不相同,也就是说它们线性无关!

现在来看看刚刚的多项式 P(x),它是 k 次的,再根据刚刚的说法,我们可以把 P(x) 表示成这些组合数的线性组合,就像这样

 \begin{equation} \label{base-poly} P(x) = \sum_{i = 0}^k {x \choose i} p_i \end{equation}

根据组合数的知识,我们可以知道当 i > x 的时候 {x \choose i} = 0,也就是说,当 x \leq k 的时候,(\ref{base-poly}) 也可以表示成这样

 \begin{equation} \label{poly0} P(x) = \sum_{i = 0}^x {x \choose i} p_i \end{equation}

这样我们可以对其进行反演得到 p_i

 \begin{equation} \label{poly1} p_i = \sum_{j = 0}^i (-1)^{i - j}{i \choose j} P(j) \end{equation}

好了,现在就是最神奇的地方了,我们要将 (\ref{poly1}) 回代,如果直接替换到 (\ref{poly0}) 显然是没有任何意义的,因为这相当于证明了一下这个反演的一个具体实例。但是,我们将其替换到 (\ref{base-poly}),虽然看起来是在做没有什么意义的事情,但是结果会有很大不同!

好,我们现在把它替换进去(过程会比较长)

 \begin{eqnarray*}
P(x) &=& \sum_{i = 0}^k {x \choose i} p_i \\
&=& \sum_{i = 0}^k {x \choose i} \sum_{j = 0}^i (-1)^{i - j}{i \choose j} P(j) \\
\end{eqnarray*}

观察到这里面似乎存在着二项式系数的交错和,而这样的和通常是可以有封闭形式的,于是考虑把 P(j) 这部分提取到外面,交换求和顺序改为枚举 P(j) 可以得到

 \begin{eqnarray*}
P(x) &=& \sum_{j=0}^k P(j) \sum_{i=j}^k (-1)^{i-j}{x \choose i}{i \choose j} \\
&=& \sum_{j=0}^k P(j) \sum_{i=0}^{k-j} (-1)^{i}{x \choose {i+j}}{{i+j} \choose j}
\end{eqnarray*}

现在考虑看看里面的那个求和能不能化简单,直接来似乎不太可能,那就考虑能否再分离出一个与 i 无关的二项式系数出来

 \begin{eqnarray*}
& &{x \choose {i+j}}{{i+j} \choose j} \\
&=&\frac{x!}{(i+j)!(x-i-j)!} \cdot \frac{(i+j)!}{i!j!} \\
&=&\frac{x!}{j!} \cdot \frac{1}{i!(x-i-j)!} \\
\end{eqnarray*}

现在看看右边的分母 i + (x - i - j) = x - j,我们想只要再在分子添一个  (x - j)! 右边就可以变成一个组合数啦!再看左边,分子添上  (x - j)! 后,(x - j) + j = x,左边也是一个组合数啦!这样刚刚的式子就可以高兴的改变成

 \begin{equation} \label{double-sum}
P(x) = \sum_{j=0}^k {x \choose j} P(j) \sum_{i=0}^{k-j} (-1)^{i}{{x-j} \choose i}
\end{equation}

到此为止,我们剩下的工作就是尝试计算上面的交错和了,这相当于要计算

 \begin{equation} \label{upper-negation} \sum_{i=0}^{m} (-1)^{i}{n \choose i} \end{equation}

首先来证明一个组合数的恒等变换

 {r \choose k} = (-1)^k {{k - r - 1} \choose k}

我们提取出这个组合数的分子部分,将每一项取负

 \begin{eqnarray*}
& &r(r - 1)(r - 2)\cdots (r - k + 1) \\
&=&(-1)^k (-r)(1 - r)(2 - r) \cdots (k - 1 - r) \\
&=&(-1)^k (k - r - 1)(k - r - 2) \cdots (k - r - k)
\end{eqnarray*}

这个变换被称为上指标反转(upper negation),我们现在对 (\ref{upper-negation}) 进行上指标反转得到

 \begin{eqnarray*}
& & \sum_{i=0}^{m} (-1)^{i}{n \choose i} \\
&=& \sum_{i=0}^m {{(-n-1) + i} \choose {i}} \\
&=& {{(-n-1) + 0} \choose {0}} + {{(-n-1) + 1} \choose {1}} + \cdots + {{(-n-1) + m} \choose {m}} \\
&=& {{(-n-1) + 1} \choose {0}} + {{(-n-1) + 1} \choose {1}} + \cdots + {{(-n-1) + m} \choose {m}} \\
&=& {{(-n-1) + 2} \choose {1}} + \cdots + {{(-n-1) + m} \choose {m}} \\
&=& {{(-n-1) + m + 1} \choose {m}} \\
&=& {{m - n} \choose {m}} \\
\end{eqnarray*}

这样,又可以把刚刚的式子 (\ref{double-sum}) 的交错和改写成封闭形式

 \begin{eqnarray*}
P(x) &=& \sum_{j=0}^k {x \choose j} P(j) \sum_{i=0}^{k-j} (-1)^{i}{{x-j} \choose i} \\
&=& \sum_{j=0}^k {x \choose j} P(j) {{(k - j) - (x - j)} \choose {k - j}} \\
&=& \sum_{j=0}^k (-1)^{k - j}{x \choose j}{{x - j - 1} \choose {k - j}} P(j)
\end{eqnarray*}

最后一行又用到一次上指标反转,现在最后的问题——如何快速计算上面的组合数!

 \begin{eqnarray*}
& & {x \choose j}{{x - j - 1} \choose {k - j}} P(j) \\
&=& \frac{x!}{(x - j)(x - k - 1)!} \cdot \frac{1}{j!(k - j)!}
\end{eqnarray*}

然后左边的部分可以先记录前缀和、后缀和,然后两边拼起来,复杂度 \mathcal O(k)-\mathcal O(1),右边的阶乘由于都不大可以用线性逆元在相同复杂度内算出来,总的复杂度就是 \mathcal O(k)

最后看到这里,你可能会说 (\ref{poly0})(\ref{base-poly}) 不是一样的么,为什么带入两个式子差别会这么大呢?原因是它们一样只是在 x \leq k 的时候,在 x > k 的时候它们却是不同的!因此产生了这个有趣的现象

顺带一提,关于它的应用,你可以用来求幂和,以及 BZOJ-4126

【本文纯属理性愉悦!】

Miskcoo's Space,版权所有丨如未注明,均为原创
转载请注明转自:http://blog.miskcoo.com/2015/08/special-polynomial-linear-interpolation

miskcoo

顺利从福州一中毕业!感觉大学周围都是聚聚十分可怕QAQ 想要联系的话欢迎发邮件:miskcoo [at] gmail [dot] com

2 thoughts on “特殊多项式在整点上的线性插值方法

Leave a Reply

Your email address will not be published. Required fields are marked *

NOTE: If you want to add mathematical formulas, use $$ to wrap them. For example, use $$x_0$$ to get $$x_0$$.

If you want to get a newline, hit Enter twice, that is, use double newlines to get a newline.