拉格朗日插值

连续的取点，时间复杂度\(O(n)\)
模板

#include <iostream>
#include <cstdio>
using namespace std;
const int N = 60, MOD = 998244353;
int n, k, fac[N], inv[N], pows[N][N], x[N], y[N];
long long quickPower (long long x, long long y) {
    long long res = 1;
    while (y) {
        if (y & 1) res = res * x % MOD;
        x = x * x % MOD;
        y >>= 1;
    }
    return res;
}
int Lagrange (int n, int *x, int *y, int k) {
    static int pre[N], suf[N];
    int ans = 0;
    pre[0] = k - x[0], suf[n + 1] = 1;
    for (int i = 1; i <= n; i ++) pre[i] = 1ll * pre[i - 1] * (k - x[i]) % MOD;
    for (int i = n; i >= 0; i --) suf[i] = 1ll * suf[i + 1] * (k - x[i]) % MOD;
    for (int i = 0; i <= n; i ++) {
        int up = 1ll * (i == 0 ? 1 : pre[i - 1]) * suf[i + 1] % MOD;
        int down = 1ll * inv[i] * inv[n - i] % MOD * ((n - i & 1) ? MOD - 1 : 1) % MOD;
        ans = (ans + 1ll * y[i] * up % MOD * down % MOD) % MOD;
    }
    return ans;
}
inline int C (int n, int m) {
    if (n < 0 || m < 0 || n < m) return 0;
    return 1ll * fac[n] * inv[m] % MOD * inv[n - m] % MOD;
}
int solve (int n, int k) {
    int ans = 0;
    for (int p = 1; p <= n; p ++)
        for (int v = 1; v <= k; v ++) {
            int x1 = v - 1, y1 = k - (v - 1), x2 = k - v, y2 = v;
            for (int i = 0; i <= p - 1; i ++)
                for (int j = i + 1; j <= n - p; j ++)
                    ans = (ans + 1ll * v * C(p - 1, i) % MOD * C(n - p, j) % MOD * pows[x1][i] % MOD * pows[y1][p - 1 - i] % MOD * pows[x2][j] % MOD * pows[y2][n - p - j] % MOD) % MOD;
        }
    return ans;
}
int main () {
    scanf("%d%d", &n, &k);
    fac[0] = inv[0] = 1;
    for (int i = 1; i <= 55; i ++) {
        fac[i] = 1ll * fac[i - 1] * i % MOD;
        inv[i] = quickPower(fac[i], MOD - 2);
    }
    for (int i = 0; i <= 55; i ++)
        for (int j = 0; j <= 55; j ++) {
            if (!j) pows[i][j] = 1;
            else pows[i][j] = 1ll * pows[i][j - 1] * i % MOD;
        }
    if (k <= n + 2) {
        printf("%d\n", solve(n, k));
        return 0;
    }
    for (int i = 0; i <= n + 2; i ++) {
        x[i] = i;
        y[i] = solve(n, i);
    }
    printf("%d\n", Lagrange(n + 2, x, y, k));
    return 0;
}

非连续的取点，时间复杂度\(O(n ^ 2)\)
模板

#include <iostream>
#include <cstdio>
using namespace std;
const int N = 2010, MOD = 998244353;
int n, k, x[N], y[N];
long long quickPower (long long x, long long y) {
    long long res = 1;
    while (y) {
        if (y & 1) res = res * x % MOD;
        x = x * x % MOD;
        y >>= 1;
    }
    return res;
}
int Lagrange (int n, int *x, int *y, int k) {
	int ans = 0;
    for (int i = 0; i <= n; i ++) {
		int inv = 1, res = 1;
		for (int j = 0; j <= n; j ++)
			if (j != i) {
				inv = 1ll * inv * ((x[i] - x[j] + MOD) % MOD) % MOD;
				res = 1ll * res * ((k - x[j] + MOD) % MOD) % MOD;
			}
		inv = quickPower(inv, MOD - 2);
		ans = (ans + 1ll * y[i] * res % MOD * inv % MOD) % MOD;
	}
	return ans;
}
int main () {
    scanf("%d%d", &n, &k);
    for (int i = 0; i < n; i ++)
		scanf("%d%d", &x[i], &y[i]);
	printf("%d\n", Lagrange(n - 1, x, y, k));
    return 0;
}