Luogu 4781 【模板】拉格朗日插值

模板题。

拉格朗日插值的精髓在于这个公式

$$f(x) = \sum_{i = 1}^{n}y_i\prod _{j \neq i}\frac{x - x_i}{x_j - x_i}$$

其中$(x_i, y_i)$是给定的$n$个点值。

代入任何一个给定的点值坐标$x_k$，都会发现这个式子等于$y_k$成立，因为对于任何$i \neq k$，后面的系数都至少有一项为$0$，而当$i == k$的时候，后面那一项一定为$1$，这样子就可以保证代进去的点值一定被满足。

因为题目中要求直接代入$x$求值，所以在算这个式子的时候直接把$x$代进去计算就可以了，时间复杂度$O(n^2)$，要不然求系数的过程相当于高斯消元，时间复杂度$O(n^3)$。

Code：

#include <cstdio>

#include <cstring>

using namespace std;

typedef long long ll;

const int N = ;

const ll P = 998244353LL;

int n;

ll k, xi[N], yi[N];

template <typename T>

inline void read(T &X) {

    X = ; char ch = ; T op = ;

    for (; ch > '' || ch < ''; ch = getchar())

        if (ch == '-') op = -;

    for (; ch >= '' && ch <= ''; ch = getchar())

        X = (X << ) + (X << ) + ch - ;

    X *= op;

}

inline ll fpow(ll x, ll y) {

    ll res = 1LL;

    for (; y > ; y >>= ) {

        if (y & ) res = res * x % P;

        x = x * x % P;

    }

    return res;

}

int main() {

    read(n), read(k);

    for (int i = ; i <= n; i++)

        read(xi[i]), read(yi[i]);

    ll ans = 0LL;

    for (int i = ; i <= n; i++) {

        ll mul1 = 1LL, mul2 = 1LL;

        for (int j = ; j <= n; j++) {

            if (i == j) continue;

            mul1 = mul1 * ((k - xi[j] + P) % P) % P;

            mul2 = mul2 * ((xi[i] - xi[j] + P) % P) % P;

        }

        ans = (ans + yi[i] * mul1 % P * fpow(mul2, P - ) % P) % P;

    }

    printf("%lld\n", ans);

    return ;

}