拉格朗日插值

· · 个人记录

拉格朗日插值法简直就是懒人必备的推公式神器

以下用一个例子加以说明

1^{2}+2^{2}+3^{2}+4^{2} ...

我们假定所有人知道它可以用一个三次的公式表示

f(x)=\sum_{i = 1}^{n}i^{2}

拉格朗日插值的用法就是用n+1个点来确定一个n次的函数解析式

(1,f(1)) (2,f(2)) (3,f(3)) (4,f(4)) f(1) = 1,f(2) = 5,f(3) = 14,f(5) = 29 (1,1)(2,5)(3,14)(5,29)

我们假设f(x)可以写成以下的形式

f(x)=y_1S_1(x)+y_2S_2(x)+y_3S_3(x)

其中 S_n 为不同的多项式，容易看出如果 x = x_1 时 S_1(x_1)=1,S_2(x_1)=0,S_3(x_1)=0 则本函数成立

所以我们只需令

S_1(x) = \frac{(x-x_2)(x-x_3)}{(x_1-x_2)(x_1-x_3)}\\ S_2(x) = \frac{(x-x_1)(x-x_3)}{(x_2-x_1)(x_2-x_3)}\\ S_3(x) = \frac{(x-x_1)(x-x_2)}{(x_3-x_1)(x_3-x_2)}

即可 然后我们将本式子带回

f(x)=y_1\frac{(x-x_2)(x-x_3)}{(x_1-x_2)(x_1-x_3)}+y_2\frac{(x-x_1)(x-x_3)}{(x_2-x_1)(x_2-x_3)}+y_3\frac{(x-x_1)(x-x_2)}{(x_3-x_1)(x_3-x_2)}

把值代入可得

f(x) = \frac{n(n+1)(2n+1)}{6}

读者可自行推导

以上便是对小学奥数的一个推导

习题：

f_k(x) = \sum_{i=1}^{x}i^{k} 
int ksm(int a, int b) {
    if (b == 0) return 1;
    if (b == 1) return a;
    int t = ksm(a, b / 2);
    t = t * t % mod;
    if (b % 2) t = t * a % mod;
    return t;
}
int xh[N], x[N], y[N];
inline void init(int n) {
    for (int i = 1 ; i <= n + 2 ; i ++)
        x[i] = i, y[i] = (y[i - 1] + ksm(i, n)) % mod;
    for (int i = 1 ; i <= n + 2 ; i ++) {
        xh[i] = 1;
        for (int j = 1 ; j <= n + 2 ; j ++)
            if (i != j)
                xh[i] = xh[i] * (x[i] - x[j]) % mod;
        xh[i] = y[i] * ksm(xh[i], mod - 2) % mod;
    }
}
inline int solve(int k, int n) {
    int res = 0;
    for (int i = 1 ; i <= n + 2 ; i ++) {
        int u = xh[i];
        for (int j = 1 ; j <= n + 2 ; j ++)
            if (i != j) 
                u = u * ((k - x[j] + mod) % mod) % mod;
        res = (res + u + mod) % mod;
    }
    return res;
}

solve用于求值，init用于预处理，xh中存系数(xh是喜欢而不是小花)

习题：P4593 [TJOI2018] 教科书般的亵渎

注：此为 O(n ^ {2}) 的做法, FFT, NNT待读者自行学习

接下来是形式化的用法

首先我们拥有 k +1 个点

(x_1,y_1)(x_2,y_2)...(x_{k+1},y_{k+1}) f_k(x)=\sum_{i = 1}^{k}y_i\prod_{j \ne i}^{n}\frac{x - x_j}{x_i - x_j}

提出系数

f_k(x) = \sum_{i=1}^{k}\frac{y_i}{\prod_{j \ne i}^{n}(x_i - x_j)}\prod_{j \ne i}^{n}(x-x_j)

以上代码中 xh 就是用于存 \frac{y_i}{\prod_{j \ne i}^{n}(x_i - x_j)}