这个东西应该在很久之前就要学的结果被鸽到了现在。
我是鸽德
拉格朗日插值
拉格朗日插值解决的是一类给定多项式的点值表示让你求另一个点的函数值的问题。
先来思考这个引子：给定 \(n\) 个点对 \((x_i,y_i)\) 和 \(k\)，保证 \(\forall i\not=j,x_i\not=x_j\)，求 \(f(k)\)。
有一个显然的线性代数写法，建立一个 \(n\times n\) 的矩阵，然后解方程即可。
时间复杂度 \(\mathcal O(n^3)\)。这个时间复杂度是比较差的。
接下来进入正题。
我们直接给出拉格朗日多项式的式子
\[f(x)=\sum_{i=1}^{n}y_i\prod_{j\not=i}\frac{x-x_j}{x_i-x_j} \]这里只给出直观解释：考虑一个点 \((x_p,y_p)\)，计算 \(f(x_p)\)，当 \(i\not=p\) 时，\(j\) 可以等于 \(p\)，于是出现了 \(x-x_p\)，答案为 \(0\)；当 \(i=p\) 时，分子和分母相等，因此有 \(f(x_p)=y_p\)。
据此，我们只要能找到一个多项式的点值表示，我们便可以求出这个多项式上任意一点的值。
代入计算，时间复杂度 \(\mathcal O(n^2)\)
接下来是一个经典应用：求 \(\sum\limits_{i=1}^{n}i^k\)，对 \(10^9+7\) 取模。
如果要用拉格朗日插值，就要明确我们要求的东西是多项式，问题转化为如何证明 \(f(x)=\sum\limits_{i=1}^{x}i^k\) 是一个项数较少的多项式。
记 \(\Delta f(x)\) 为 \(f(x)\) 的差分数组，\(\Delta^2f(x)\) 为 \(f(x)\) 的二阶差分数组，即 \(\Delta^2f(x) = \Delta(\Delta f(x))\)。
如果我们令 \(\Delta^0f(x)=f(x)\)，我们可以递归地得到如下定义 \(p\in \mathbb N^*,\Delta^pf(x)=\Delta(\Delta^{p-1}f(x))\)，称其为 \(f(x)\) 的 \(p\) 阶差分。
如果 \(\Delta^pf(x)\) 是一个常数序列，则 \(f(x)\) 是 \(p\) 阶等差数列。
引理：如果数列 \(\{a_n\}\) 是一个 \(p\) 阶等差数列，那么 \(a_n\) 是关于 \(n\) 的一个 \(p\) 次多项式，即 \(a_n=k_pn^p+k_{p-1}n^{p-1}+\dots+k_0\)。
证明：假设 \(a\) 数列的通项是一个关于 \(n\) 的一个 \(p\) 次多项式，那么 \(a_x = \sum\limits_{i=0}^{p}k_ix^i\)，据此可得到
\[\begin{align*} \Delta a(x) & = a(x+1)-a(x) \\ ~ & = \sum_{i=0}^{p}k_i(x+1)^i - \sum_{i=0}^{p}k_ix^i \end{align*} \]注意到两项的 最高次项系数是相等的，相减后消去，因此，\(\Delta a(x)\) 的次数是 \(a(x)\) 的次数减一。\(p\) 次差分后，得到 \(0\) 次式，即常数序列。
证毕。
本题，可以定义数列 \(\{a_n\}\) 为
\[\sum_{i=1}^{1}i^k,\sum_{i=1}^{2}i^k,\sum_{i=1}^{3}i^k,\dots,\sum_{i=1}^{n}i^k \]两两做差，发现序列变成了 \(1^k,2^k,\dots,n^k\)（这里在第一项前补了 \(0\)）。
通项为 \(a_x=x^k\)，是 \(k\) 次式，根据引理，\(\{a_n\}\) 应该是一个 \(k+1\) 次式。
朴素拉格朗日插值 \(\mathcal O(k^2)\)，是否有更优的做法？
注意到我们可以代入的点可以自选，所以我们可以寻找一批有特殊性质的点。我们尝试用 \(1\) 到 \(k+2\) 代入。
令 \(x_i=i,y_i=\sum\limits_{j=1}^{i}j^k\)
\[f(n)=\sum_{i=1}^{k+2}y_i\prod_{j\not=i}\frac{n-x_j}{x_i-x_j} \]注意到，分母是 \(\prod_{j=1}^{i-1}\prod_{j=i-k-2}^{-1}\)，可以预处理，分子是 \(\prod_{j=n-i-1}^{n-1}\prod_{j=n-k-2}^{n-i+1}\)，可以预处理出前缀后缀乘积。
预处理 \(\mathcal O(k)\)。
如果你认为上面这道题很简单，那就快来做一下例题吧！
标签：拉格朗,插值,多项式,sum,Delta,prod From： https://www.cnblogs.com/misterrabbit/p/17230632.html