求多项式

我们知道 $n$ 个点可以确定 $n-1$ 次多项式（比如三点求抛物线）。

假设 $f(x)=\sum_{i=0}^{n-1}a_ix^i$ ，如果我们要求 $f(k)$ ，可以先解出 $\{a\}$ 。把这 $n$ 个点代进去得到 $n$ 个方程，就可以高斯消元解出系数，但是这样是 $O(n^3)$ 的。

拉格朗日插值

假设第 $i$ 个点为 $P_i(x_i,y_i)$ ，令 $H_i(x_i,0)$ 为 $P_i$ 在 $x$ 轴上的射影。

考虑这样一种构造 $f(x)$ 的方法：定义 $g_i(x)$ 表示过 $\{P_i\}\cup\{H_j|j\not=i\}$ 点集的多项式，那么只要将所有 $g_i(x)$ 加起来就可以得到 $f(x)$ ，因为当 $x=x_i$ 时，除了 $g_i(x)$ 之外，其他的 $g_j(x)$ 都是 $0$ 。

所以我们只需要构造出 $g_i(x)$ 即可，直接上结论：

$$ g_i(x)=y_i\prod_{j\not=i}{x-x_j\over x_i-x_j} $$

试着将任意 $x=x_i$ 代入显然成立，因此：

$$ f(x)=\sum_{i=1}^{n}y_i\prod_{j\not=i}{x-x_j\over x_i-x_j} $$

但是不难发现，如果要求出系数，还是需要 $O(n^3)$ 的复杂度（或者使用分治+FFT，$O(n^2\log_2^2n)$ ，常数极大）。不过，如果我们要求 $f(k)$ ，就可以 $O(n^2)$ 直接代入了：

$$ f(k)=\sum_{i=1}^{n}y_i\prod_{j\not=i}{k-x_j\over x_i-x_j} $$

优化

令 $A(k)=\prod_{i=1}^{n}(k-x_i),w_i=\prod_{j\not=i}(x_i-x_j)$ ，则：

$$ \begin{aligned} f(k)&=A(k)\sum_{i=1}^{n}{y_i\over (k-x_i)\prod_{j\not=i}(x_i-x_j)}\\ &=A(k)\sum_{i=1}^{n}{y_i\over (k-x_i)w_i}\\ \end{aligned} $$

这样有什么好处呢？不难发现 $A(k)$ 和后面那部分是独立的，也就是说对于每个 $k$ 我们可以 $O(n)$ 求出 $f(k)$ ！

而且还可以支持 $O(n)$ 动态加点，只需要维护 $w_i$ 即可。

模板题

LOJ165 拉格朗日插值

#include<cstdio>
using namespace std;
typedef long long LL;
const int maxn=3000,MOD=998244353;

int te,n,X[maxn+5],Y[maxn+5],w[maxn+5];

#define ADD(x,y) (((x)+(y))%MOD)
#define MUL(x,y) ((LL)(x)*(y)%MOD)
int Pow(int w,int b) {int s=1;while (b) {if (b&1) s=MUL(s,w);w=MUL(w,w);b>>=1;} return s;}
int main(){
    freopen("165.in","r",stdin);freopen("165.out","w",stdout);
    for (scanf("%d",&te);te;te--){
        int tp;scanf("%d",&tp);
        if (tp==1){
            n++;scanf("%d%d",&X[n],&Y[n]);
            w[n]=1;for (int i=1;i<n;i++) w[n]=MUL(w[n],X[n]+MOD-X[i]);
            for (int i=1;i<n;i++) w[i]=MUL(w[i],X[i]+MOD-X[n]);
        } else {
            int K,A=1,ans=0,k=0;scanf("%d",&K);
            for (int i=1;i<=n;i++) if (K!=X[i]) A=MUL(A,K+MOD-X[i]); else k=i;
            if (k) {printf("%d\n",Y[k]);continue;}
            for (int i=1;i<=n;i++) ans=ADD(ans,MUL(Y[i],Pow(MUL(K+MOD-X[i],w[i]),MOD-2)));
            ans=MUL(ans,A);printf("%d\n",ans);
        }
    }
    return 0;
}