朴素方法

n 个点 (x_i,y_i) 可以唯一地确定一个多项式 y = f(x)。

给定这 n 个点，请你确定这个多项式，并求出 f(k) \bmod 998244353 的值。

#include <bits/stdc++.h>
using namespace std;
const int P = 998244353;
const int N = 2005;
int n, k;

int ksm(int a, int b) {}
int ni(int a) {}

vector<int> x, y;
int Lagrange(vector<int> &x, vector<int> &y, int k) {
    int n = (int)x.size(), 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 * (k - x[j] + P) % P;
                s2 = 1LL * s2 * (x[i] - x[j] + P) % P;
            }
        }
        (ans += 1LL * y[i] * s1 % P * ni(s2) % P) %= P;
    }
    return ans;
}


int main() {
    scanf("%d%d", &n, &k);
    x.resize(n); y.resize(n);
    for(int i = 0; i < n; i++) {
        scanf("%d%d", &x[i], &y[i]);
    }
    printf("%d\n", Lagrange(x, y, k));
    return 0;
}

重心法插值

可以支持 O(n) 动态加点。

#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
const int P = 998244353;
const int N = 2005;
int n, k;

int ksm(int a, int b) {}
int ni(int a) {}

struct Interpolation {
    int g = 1, t[N];
    vector<int> x, y;
    int Lagrange(int k) {
        int n = (int)x.size(), s = 0; g = 1;
        for (int i = 0; i < n; i++) g = 1LL * g * (k - x[i] + P) % P;
        for (int i = 0; i < n; i++) {
            int tmp1 = 1, tmp2, tmp3;
            for (int j = 0; j < n; j++) if (i != j) {
                tmp1 = 1LL * (x[i] - x[j] + P) * tmp1 % P;
            }
            tmp2 = 1LL * y[i] * ni(tmp1) % P;
            tmp3 = (k - x[i] + P) % P;
            t[i] = 1LL * tmp2 * ni(tmp3) % P;
            s = (s + t[i]) % P;
        }
        return 1LL * g * s % P;
    }
    int add(int X, int Y, int k) {
        int n = (int)x.size(), s = 0, tmp1 = 1, tmp2, tmp3;
        x.push_back(X); y.push_back(Y);
        g = 1LL * g * (k-X+P) % P;
        for (int i = 0; i < n; i++) {
            t[i] = 1LL * t[i] * ni(x[i] - X + P) % P;
            tmp1 = 1LL * tmp1 * (X-x[i]+P) % P;
        }
        tmp2 = 1LL * Y * ni(tmp1) % P;
        tmp3 = (k - X + P) % P;
        t[n] = 1LL * tmp2 * ni(tmp3) % P;
        for (int i = 0; i <= n; i++) s = (s + t[i]) % P;
        return 1LL * g * s % P;
    }
}I;

int main() {
    scanf("%d%d", &n, &k);
    for(int i = 0, a, b; i < n - 1; i++) {
        scanf("%d%d", &a, &b);
        I.x.push_back(a); I.y.push_back(b);
    }
    int X, Y; scanf("%d%d", &X, &Y);
    I.Lagrange(k);
    printf("%d\n", I.add(X, Y, k));
    return 0;
}

连续值的插值

适用： x 值为连续（不一定从 1 开始）。

int r[N], s[N];
int Lagrange(vector<int> &x, vector<int> &y, ll X) {
    int n = (int)y.size() - 1, ans = 0; X %= P;
    r[0] = (X - x[0] + P) % P; s[n + 1] = 1;
    for (int i = 1; i <= n; i++) {
        r[i] = 1LL * r[i - 1] * (X - x[i]) % P;
    }
    for (int i = n; i >= 0; i--) {
        s[i] = 1LL * s[i + 1] * (X - x[i]) % P;
    }
    for (int i = 0; i <= n; i++)
        (ans += 1LL * y[i] * (i == 0 ? 1 : r[i - 1]) % P * s[i + 1] % P
         * ifac[i] % P * (((n - i)&1) ? -1 : 1) * ifac[n - i] % P) %= P;
    return (ans + P) % P;
}

应用-求幂和

题目链接：CF622F The Sum of the k-th Powers

题目大意：求：

\sum_{i=1}^{n}i^k

#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
const int P = 1e9 + 7;
const int N = 1e6 + 10;
int n, k;

int ifac[N];
void pre() {
    ifac[0] = ifac[1] = 1;
    for (int i = 2; i < N; i++) {
        ifac[i] = -1LL * P / i * ifac[P % i] % P;
    }
    for (int i = 2; i < N; i++) {
        ifac[i] = 1LL * ifac[i] * ifac[i - 1] % P;
    }
}

int ksm(int a, int b) {
    int ret = 1;
    for (; b; b >>= 1, a = 1LL * a * a % P) {
        if (b & 1) ret = 1LL * ret * a % P;
    }
    return ret;
}

struct qm {
    vector<int> y;
    int a[N], b[N];
    void init(int k) {
        y.resize(1); y[0] = 0;
        for (int i = 1; i <= k + 1; i++) {
            y.push_back((y.back() + ksm(i, k)) % P);
        }
    }
    int Lagrange(ll X) {
        int n = (int)y.size() - 1, ans = 0; X %= P;
        a[0] = (int)X; b[n + 1] = 1;
        for (int i = 1; i <= n; i++) {
            a[i] = 1LL * a[i - 1] * (X - i) % P;
        }
        for (int i = n; i >= 0; i--) {
            b[i] = 1LL * b[i + 1] * (X - i) % P;
        }
        for (int i = 0; i <= n; i++)
            (ans += 1LL * y[i] * (i == 0 ? 1 : a[i - 1]) % P * b[i + 1] % P
             * ifac[i] % P * (((n - i)&1) ? -1 : 1) * ifac[n - i] % P) %= P;
        return (ans + P) % P;
    }
    int solve(ll n) {
        return Lagrange(n);
    }
}I;
int main() {
    pre();
    scanf("%d%d", &n, &k);
    I.init(k);
    printf("%d\n", I.solve(n));
    return 0;
}