10
同步发布于 我的 cnblogs
这篇应该比较简单（）
LAGRANGE 插值
> 给出 nnn 个点 (xi,yi)(x_i,y_i)(xi ,yi ) 满足 xi≠xjx_i\neq x_jxi =xj ，可以唯一确定一个 n−1n-1n−1 次多项式 y=f(x)y=f(x)y=f(x) 过上述所有 nnn 个点。
>
> 现在给出 kkk，求 f(k)f(k)f(k) 的值。
一个简单的想法是直接 Gauss 消元，可以 O(n3)O(n^3)O(n3) 解出这个 n−1n-1n−1 次多项式每一项的系数。
这里介绍一下用 Lagrange 插值的解法：
* 构造 nnn 个函数 fi(x)f_i(x)fi (x) 表示该函数过点 (xi,yi)(x_i,y_i)(xi ,yi )，对于任意 j≠ij\neq ij=i 都过点 (xj,0)(x_j,0)(xj ,0)。容易发现令 f(x)=∑i=1nfi(x)f(x)=\sum\limits_{i=1}^nf_i(x)f(x)=i=1∑n fi (x) 就可以得到一个满足条件的函数 f(x)f(x)f(x)。
* 然后考虑构造因式分解：对于每个 fi(x)f_i(x)fi (x) 多项式构造一项 x−xj(i≠j)x-x_j(i\neq j)x−xj (i=j)，然后凑一个系数 aia_iai 满足 fi(xi)=yif_i(x_i)=y_ifi (xi )=yi ，容易解方程得到 ai=yi∏j≠i(xi−xj)a_i=\dfrac{y_i}{\prod\limits_{j\neq i}(x_i-x_j)}ai =j=i∏ (xi −xj )yi 。
* 于是有：f(k)=∑i=1nfi(k)=∑i=1nyi∏j≠ik−xjxi−xjf(k)=\sum\limits_{i=1}^nf_i(k)=\sum\limits_{i=1}^ny_i\prod\limits_{j\neq i}\frac{k-x_j}{x_i-x_j}f(k)=i=1∑n fi (k)=i=1∑n yi j=i∏ xi −xj k−xj ，可以在 O(n2)O(n^2)O(n2) 的时间复杂度内求解。
:::success[O(n2logn)O(n^2\log n)O(n2logn) 解法]
:::
:::success[O(n2)O(n^2)O(n2) 解法]
:::
001. P5667 拉格朗日插值2
根据上面的理论，容易得到：
f(m+k)=∑i=0nyi∏j≠im+k−ji−jf(m+k)=\sum\limits_{i=0}^ny_i\prod\limits_{j\neq i}\frac{m+k-j}{i-j} f(m+k)=i=0∑n yi j=i∏ i−jm+k−j
可以 O(n2)O(n^2)O(n2) 时间复杂度求解。
考虑对这个东西进行优化。注意到 kkk 的取值是连续的一段，所以从这里突破：
f(m+k)=∑i=0nyi∏j≠im+k−ji−j=∑i=0nyi∏j≠i(m+k−j)∏j≠i1i−j=∑i=0nyi(m+k)!(m+k−n−1)!(−1)n−i1i!(n−i)!(m+k−i)=(m+k)!(m+k−n−1)!∑i=0nyi(−1)n−i1i!(n−i)!(m+k−i)=(m+k)!(m+k−n−1)!∑i=0n[1i!×yi×(−1)n−i1(n−i)!]×1m+k−i\begin{aligned} f(m+k) &=\sum\limits_{i=0}^ny_i\prod\limits_{j\neq i}\frac{m+k-j}{i-j}\\
&=\sum\limits_{i=0}^ny_i\prod\limits_{j\neq i}(m+k-j)\prod\limits_{j\neq i}\frac1{i-j}\\ &=\sum\limits_{i=0}^ny_i\frac{(m+k)!}{(m+k-n-1)!}(-1)^{n-i}\frac1{i!(n-i)!(m+k-i)}\\ &=\frac{(m+k)!}{(m+k-n-1)!}\sum\limits_{i=0}^ny_i(-1)^{n-i}\frac1{i!(n-i)!(m+k-i)}\\
&=\frac{(m+k)!}{(m+k-n-1)!}\sum\limits_{i=0}^n\left[\frac1{i!}\times y_i\times(-1)^{n-i}\frac1{(n-i)!}\right]\times \frac1{m+k-i} \end{aligned} f(m+k) =i=0∑n yi j=i∏ i−jm+k−j =i=0∑n yi j=i∏ (m+k−j)j=i∏ i−j1 =i=0∑n yi (m+k−n−1)!(m+k)! (−1)n−ii!(n−i)!(m+k−i)1 =(m+k−n−1)!(m+k)! i=0∑n yi
(−1)n−ii!(n−i)!(m+k−i)1 =(m+k−n−1)!(m+k)! i=0∑n [i!1 ×yi ×(−1)n−i(n−i)!1 ]×m+k−i1
记 Pi=(m+i)!(m+i−n−1)!,Ai=1i!×yi×(−1)n−i1(n−i)!,Bi=1m+iP_i=\frac{(m+i)!}{(m+i-n-1)!},A_i=\frac1{i!}\times y_i\times(-1)^{n-i}\frac1{(n-i)!},B_i=\frac1{m+i}Pi =(m+i−n−1)!(m+i)! ,Ai =i!1 ×yi ×(−1)n−i(n−i)!1 ,Bi =m+i1 ，则可以用 NTT 求出 C=A⊙BC=A\odot BC=A⊙B 即 CCC 为 A,BA,BA,B 两个序列的等差卷积，而 PiP_iPi 显然可以线性递推。
但是这真的对吗？？？把卷积形式写出来之后发现其形如：Ck=∑iAiBk−iC_k=\sum\limits_iA_iB_{k-i}Ck =i∑ Ai Bk−i （0≤i≤n0\le i\le n0≤i≤n），这怎么还出来负数下标了（）不过解决这个问题也是简单的，重新记 Bi=1m+i−nB_i=\frac1{m+i-n}Bi =m+i−n1 ，此时有 Cn+k=∑i=0nAiBn+k−iC_{n+k}=\sum\limits_{i=0}^nA_iB_{n+k-i}Cn+k =i=0∑n Ai Bn+k−i ，将其写成卷积的形式只需要对所有 i>ni>ni>n 都记 Ai=0A_i=0Ai =0
就可以扩展为 Cn+k=∑i=0n+kAiBn+k−iC_{n+k}=\sum\limits_{i=0}^{n+k}A_iB_{n+k-i}Cn+k =i=0∑n+k Ai Bn+k−i 的形式。
一次 NTT 卷积即可求出 C=A⊙BC=A\odot BC=A⊙B 这个等差卷积。
因此总时间复杂度为 O(nlogn+m)O(n\log n+m)O(nlogn+m)，分段打表阶乘可以把后面的 O(m)O(m)O(m) 省去。
跑了 973ms，喜提最劣解（没事至少这个能过）
:::success[Code]
:::
006. CF622F THE SUM OF THE K-TH POWERS
通过作差可以发现答案是一个 k+1k+1k+1 次多项式的形式，因此想到 Lagrange 插值。将 xi=ix_i=ixi =i（0≤i≤n0\le i\le n0≤i≤n）带入，有：
∑i=0nyi∏j≠ix−ji−j=∑i=0nyi(∏j=0i−1x−ji−j∏j=i+1nx−ji−j)=∑i=0nyi(∏j=0i−1(x−j)∏j=i+1n(x−j)∏j=0i−11i−j∏j=i+1n1i−j)=∑i=0nyi(−1)n−i1x!1(n−x+2)!∏j=0i+1(x−j)∏j=i+1n(x−j)\begin{aligned} &\sum\limits_{i=0}^ny_i\prod\limits_{j\neq i}\frac{x-j}{i-j}\\
=&\sum\limits_{i=0}^ny_i(\prod\limits_{j=0}^{i-1}\frac{x-j}{i-j}\prod\limits_{j=i+1}^n\frac{x-j}{i-j})\\ =&\sum\limits_{i=0}^ny_i(\prod\limits_{j=0}^{i-1}(x-j)\prod\limits_{j=i+1}^n(x-j)\prod\limits_{j=0}^{i-1}\frac1{i-j}\prod\limits_{j=i+1}^n\frac1{i-j})\\
=&\sum\limits_{i=0}^ny_i(-1)^{n-i}\frac1{x!}\frac1{(n-x+2)!}\prod\limits_{j=0}^{i+1}(x-j)\prod\limits_{j=i+1}^n(x-j) \end{aligned} === i=0∑n yi j=i∏ i−jx−j i=0∑n yi (j=0∏i−1 i−jx−j j=i+1∏n i−jx−j )i=0∑n yi (j=0∏i−1 (x−j)j=i+1∏n (x−j)j=0∏i−1 i−j1 j=i+1∏n i−j1 )i=0∑n yi (−1)n−ix!1 (n−x+2)!1 j=0∏i+1
(x−j)j=i+1∏n (x−j)
后面这两个 ∏\prod∏ 一看就很能预处理，而前面的显然可以直接算。时间复杂度为 O(nlogn)O(n\log n)O(nlogn)。注意到 iki^kik 是积性函数，所以使用线性筛可以将其优化至严格 O(n)O(n)O(n) 求解。
007. P4593 [TJOI2018] 教科书般的亵渎
设 S(n,k)=∑i=1nikS(n,k)=\sum\limits_{i=1}^ni^kS(n,k)=i=1∑n ik，则容易观察到该题要求的答案为：∑i=0mS(n−ai,m+1)+∑i=0m∑j=i+1m(aj−ai)m+1\sum\limits_{i=0}^mS(n-a_i,m+1)+\sum\limits_{i=0}^m\sum\limits_{j=i+1}^m(a_j-a_i)^{m+1}i=0∑m S(n−ai ,m+1)+i=0∑m j=i+1∑m (aj −ai )m+1。后半部分可以暴力快速幂求解，而前半部分是 CF622F，直接套用上面的公式求解即可。
有帮助，赞一个