定义

给定 nn 个点 (xi,yi)(x_i,y_i) 满足 xi≠xj(i≠j)x_i\neq x_j(i\neq j)，它们能唯一确定一个 n−1n-1 次的多项式 f(x)f(x)：

f(x)=∑i=1nyi∏j≠ix−xjxi−xjf(x)=\sum_{i=1}^{n}y_i\prod_{j\neq i}\frac{x-x_j}{x_i-x_j}

容易验证，带入 f(xk)f(x_k)，当 i≠ki\neq k 时，后面的那个乘积总会有 00；当 i=ki=k 时，后面的乘积为 11，并且这个多项式是 n−1n-1 次的。

[LGP5667] 拉格朗日插值2

这个题目相较于模板题更为常见，给定的 xi=ix_i=i。

设 hi=f(m+i)h_i=f(m+i)，数据范围保证了 m>nm>n，要求的是 h0∼hnh_0\sim h_n。

列式子：

hk=∑i=0nyi∏j≠im+k−ji−j=(m+k)n+1‾∑i=0nyii!(n−i)!(m+k−i)(−1)n−i=(m+k)n+1‾∑i=0nfim+k−i\begin{aligned} h_k&=\sum_{i=0}^n y_i\prod_{j\neq i}\frac{m+k-j}{i-j}\\ &=(m+k)^{\underline{n+1}}\sum_{i=0}^n \frac{y_i}{i!(n-i)!(m+k-i)(-1)^{n-i}}\\ &=(m+k)^{\underline{n+1}}\sum_{i=0}^n \frac{f_i}{m+k-i}\\ \end{aligned}

其中 fi=yii!(n−i)!(−1)n−if_i=\cfrac{y_i}{i!(n-i)!(-1)^{n-i}}，这是可以 O(n)O(n) 预处理出来的。

观察这个形式，我们希望右边是卷积 ∑i=0kfigk−i\sum_{i=0}^k f_ig_{k-i} 的样子，但是这个求和是到 nn，所以我们需要进行一步转化。

具体地说，令 gn+k−i=1m+k−ig_{n+k-i}=\cfrac{1}{m+k-i}，则 gi=1m−n+ig_i=\cfrac{1}{m-n+i}，就有：

hk=(m+k)n+1‾∑i=0n+kfign+k−ih_k=(m+k)^{\underline{n+1}}\sum_{i=0}^{n+k} f_i g_{n+k-i}

当 i>ni>n 时，fi=0f_i=0，所以这和原式是等价的。

于是，我们只要预处理出 f,gf,g 数组，做卷积 c=f∗gc=f*g，就有 hk=(m+k)n+1‾cn+kh_k=(m+k)^{\underline{n+1}}c_{n+k}，前面的下降幂维护一个窗口即可。

AC Code。

[CF622F] The Sum of the k-th Powers

首先 S(x)=∑i=1xikS(x)=\sum_{i=1}^x i^k 是一个 k+1k+1 次的多项式，于是我们可以根据 (j,∑i=0jik)(j,\sum_{i=0}^j i^k) 令 j=0∼k+1j=0\sim k+1 即可插值出这样一个多项式 S(x)S(x)。

我们只需要求 S(n)S(n) 这个点处的值，当 n≤k+1n\le k+1 时我们直接把预处理的信息输出即可，当 n>k+1n>k+1 时我们带入公式：

Sn=∑i=0k+1Si∏i≠jn−ji−j=∑i=0k+1Sink+2‾i!(k+1−i)!(−1)k+1−i(n−i)=nk+2‾∑i=0k+1Sii!(k+1−i)!(−1)k+1−i(n−i)\begin{aligned} S_n&=\sum_{i=0}^{k+1}S_i\prod_{i\neq j}\frac{n-j}{i-j}\\ &=\sum_{i=0}^{k+1} S_i\frac{n^{\underline{k+2}}}{i!(k+1-i)!(-1)^{k+1-i}(n-i)}\\ &=n^{\underline{k+2}}\sum_{i=0}^{k+1} \frac{S_i}{i!(k+1-i)!(-1)^{k+1-i}(n-i)} \end{aligned}

直接 O(klog⁡P)O(k\log P) 做即可，其中 PP 是模数。

AC Code。

[ICPC2019 Nanchang Inventional] Polynomial

首先我们要清楚，对于 S(x)=∑i=0xf(i)S(x)=\sum_{i=0}^x f(i) 是一个 n+1n+1 次的多项式，所以我们可以通过 (j,S(j))(j,S(j)) 其中 j=0∼n+1j=0\sim n+1 来唯一地确定这个多项式。

因此我们可以通过一次拉格朗日插值求出 f(n+1)f(n+1)，然后对 ff 求前缀和即可得到 S0∼Sn+1S_0\sim S_{n+1}。

对于每次询问，求 SR−SL−1S_R-S_{L-1} 即可，复杂度为 O(Tmnlog⁡P)O(Tmn\log P)，其中 PP 是模数。

AC Code。

[ICPC2021 Brazil Subregional] Assigning Prizes

设 dp(i,j)dp(i,j) 表示 xi=jx_i=j 时，i∼ni\sim n 的方案数。

转移显然有 dp(i,j)=∑k=pi+1jdp(i+1,k)=S(i+1,j)−S(i+1,pi+1−1)dp(i,j)=\sum_{k=p_{i+1}}^j dp(i+1, k)=S(i+1, j)-S(i+1, p_{i+1}-1)，并且当 S(n,j)=j−pn+1(j≥pn)S(n,j)=j-p_n+1(j\ge p_n)。

注意，这里 pi←max⁡j=inpjp_i\gets \max_{j=i}^n p_j，我们希望当 j<pij<p_i 时， dp(i,j)=0dp(i,j)=0。

观察这个关系，我们可以看出，S(n,x)S(n,x) 是一条直线，而 S(n−1,x)S(n-1,x) 是连续的 S(n,y)S(n,y) 的和，所以它是一个二次的曲线，以此类推，可以推出 S(i,x)S(i,x) 能确定一个 n−i+1n-i+1 次的多项式。

然而，如果你直接这样做，是无论如何也无法维护好 dpdp 和 SS 的关系的，因为前后位置的下标对应都不一样。

因此，由于 (pi,S(i,pi))∼(R,S(i,R))(p_i,S(i,p_i))\sim (R,S(i,R)) 这些点在一个 n−i+1n-i+1 次的多项式上，我们令 (0,S(i,0))∼(pi−1,S(i,pi−1))(0,S(i,0))\sim (p_i-1,S(i,p_i-1)) 也在这个多项式上。

拓展完定义后我们需要保证当题目数据给出 p1>Rp_1>R 时，程序输出 00，这里需要特判。

那么对于 S(i,x)S(i, x) 这个多项式，我们可以先根据文章一开头给出的递推式计算出 dp(i,x)dp(i, x)。由于 S(i+1,x)S(i+1,x) 是一个 n−in-i 次的多项式，那么连续的和就是一个 n−i+1n-i+1 次的多项式。

对于 ∏j=0i−1(x−j)∏j=i+1deg(x−j)\prod_{j=0}^{i-1} (x-j)\prod_{j=i+1}^{deg}(x-j) 我们需要预处理前缀后缀积，让拉格朗日插值的复杂度单次为 O(n)O(n)。上面题目并没有卡 log⁡P\log P 的做法，这个题目卡了，所以最终的复杂度为 O(n2)O(n^2)。

AC Code。