题解 P4781 【【模板】拉格朗日插值】

# 拉格朗日插值法 ## 简介 给定 $n + 1$ 个**横坐标不相同**的点，可以唯一确定一个 $n$ 次的多项式。最直观的求多项式的做法就是列方程求解。但是这样需要 $O(n^3)$ 的时间来计算。而拉格朗日插值法则通过构造的方法，得到了一个经过 $n + 1$ 个点的 $n$ 次多项式。 具体的过程是这样的，假设现在我们得到了 $n + 1$ 个点： $$ (x_0, y_0), \;(x_1, y_1),\; \dots,\;(x_n, y_n) $$ 设**拉格朗日基本多项式**为 $$ \ell_j(x) = \prod_{i = 0, i \neq j}^n {x - x_i \over x_j - x_i} $$ 这个基本多项式构造十分巧妙，因为注意到 $\ell_j(x_j) = 1$ ，并且 $\ell_j(x_i) = 0, \;\forall i \neq j$ 。那么，接着构造出这个 $n$ 次多项式 $$ P(x) = \sum_{i = 0}^n y_i\ell_i(x) $$ 根据基本多项式的性质，我们可以知道 $P(x_i) = y_i$ ，也就是经过了这 $n + 1$ 个点。 通过简单的多项式乘法和多项式除法就可以在 $O(n^2)$ 的时间求出这个多项式的系数表达。 ## 求解 已知 $n$ 次多项式 $f(n)$ 上的 $n+1$ 个点 $(x_i,y_i),i\in[0,n]$ ，求 $f(xi)$ ```cpp int lagrange(int n, int *x, int *y, int xi) { int ans = 0; for (int i = 0; i <= n; i++) { int s1 = 1, s2 = 1; for (int j = 0; j <= n; j++) if (i != j) { s1 = 1ll*s1*(xi-x[j])%mod; s2 = 1ll*s2*(x[i]-x[j])%mod; } ans = (1ll*ans+1ll*y[i]*s1%mod*quick_pow(s2, mod-2)%mod)%mod; } return (ans+mod)%mod; } ``` 如果 $x$ 的取值是连续一段的话，我们可以做到 $O(n)$ 求解。假设 $\forall i<j,x_i<x_j$ （具体公式推导的话，如果你有兴趣可以参看之后的内容。因为比较显然，这里不再讲解。） ```cpp int lagrange(int n, int *x, int *y, int xi) { int ans = 0; s1[0] = (xi-x[0])%mod, s2[n+1] = 1; for (int i = 1; i <= n; i++) s1[i] = 1ll*s1[i-1]*(xi-x[i])%mod; for (int i = n; i >= 0; i--) s2[i] = 1ll*s2[i+1]*(xi-x[i])%mod; ifac[0] = ifac[1] = 1; for (int i = 2; i <= n; i++) ifac[i] = -1ll*mod/i*ifac[mod%i]%mod; for (int i = 2; i <= n; i++) ifac[i] = 1ll*ifac[i]*ifac[i-1]%mod; for (int i = 0; i <= n; i++) (ans += 1ll*y[i]*(i == 0 ? 1 : s1[i-1])%mod*s2[i+1]%mod *ifac[i]%mod*(((n-i)&1) ? -1 : 1)*ifac[n-i]%mod) %= mod; return (ans+mod)%mod; } ```