拉格朗日差值公式

特殊情况

如果$P$是一个关于$x$的$n$次多项式,我们已经知道$P(i), i\in [0, n]$的值,则

$P(x) = \sum_{i = 0}^{n} (-1)^{n - i} P(i) \frac{x(x-1)(x-2)\cdots (x-n)}{(n-i)!i!(x-i)}$

一般情况

给出$n+1$个点$x_i$以及值$P(x_i)$,则

$P(x) = \sum_{i=0}^{n}P(x_i) \prod_{j=0,j\neq i}^n \frac{x-x_j}{x_i-x_j}$

例题

洛谷P4781

#include <bits/stdc++.h>

using namespace std;

using ll = long long;

const ll p = 998244353;
const int N = 2e3 + 10;

ll qpow(ll x, ll n) {
    ll res = 1;
    while (n) {
        if (n & 1)
            res = res * x % p;
        x = x * x % p;
        n >>= 1;
    }
    return res;
}

int n, k;
ll x[N], y[N];

ll gao(ll n, ll K) {
    ll res = 0;
    for (int i = 0; i <= n; ++i) {
        ll tmp = 1;
        for (int j = 0; j <= n; ++j) {
            if (i == j)
                continue;
            tmp = 1ll * tmp * (K - x[j]) % p * qpow(x[i] - x[j], p - 2) % p;
        }
        res = (res + y[i] * tmp % p + p) % p;
    }
    return res;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr), cout.tie(nullptr);

    cin >> n >> k;
    --n;
    for (int i = 0; i <= n; ++i) {
        cin >> x[i] >> y[i];
    }
    ll res = gao(n, k);
    cout << res << endl;
    return 0;
}

The 2019 ICPC China Nanchang National Invitational and International Silk-Road Programming Contest - B Polynomial

题意:给出一个关于$x$的$n$次多项式的$f(i), i\in [0, n]$,问$\sum_{i=L}^{R} f(i) \mod 9999991$

思路:已知一个关于$x$的$n$次多项式的前缀和为一个关于$x$的$n+1$次多项式,于是通过拉格朗日差值得到$f(n+1)$然后再进行拉格朗日差值得到
$\sum_{i=0}^{L} f(i)$以及$\sum_{i=0}^{R} f(i)$,减一减就可以得到答案

#include <bits/stdc++.h>

using namespace std;

#define dbg(x...)             \
    do {                      \
        cout << #x << " -> "; \
        err(x);               \
    } while (0)

void err() {
    cout << endl;
}

template <class T, class... Ts>
void err(const T& arg, const Ts&... args) {
    cout << arg << ' ';
    err(args...);
}

#define endl "\n"
#define all(A) A.begin(), A.end()
using pII = pair<int, int>;
using ll = long long;
using db = double;

const int INF = 0x3f3f3f3f;
const int N = 1e3 + 10, M = 1e7 + 10;
const ll p = 9999991;

ll qpow(ll x, ll n) {
    ll res = 1;
    while (n) {
        if (n & 1)
            res = res * x % p;
        x = x * x % p;
        n >>= 1;
    }
    return res;
}

int n, m;
ll f[N], fac[N], facinv[N];
ll inv[M];

ll gao(int _n, int x) {
    if (x <= _n)
        return f[x];
    int t = (_n & 1) ? -1 : 1;
    ll res = 0, base = 1;
    for (int i = 0; i <= _n; ++i) {
        base = base * (x - i) % p;
    }
    for (int i = 0; i <= _n; ++i, t *= -1) {
        res += 1ll * t * f[i] * base % p * facinv[_n - i] % p * facinv[i] % p *
               inv[x - i] % p;
        res = (res + p) % p;
    }
    return res;
}

void RUN() {
    fac[0] = 1ll;
    for (int i = 1; i < N; ++i)
        fac[i] = fac[i - 1] * i % p;
    facinv[N - 1] = qpow(fac[N - 1], p - 2);
    for (int i = N - 1; i >= 1; --i)
        facinv[i - 1] = facinv[i] * i % p;
    inv[1] = 1;
    for (int i = 2; i < p; ++i)
        inv[i] = inv[p % i] * (p - p / i) % p;
    int T;
    scanf("%d", &T);
    while (T--) {
        scanf("%d %d", &n, &m);
        for (int i = 0; i <= n; ++i) {
            scanf("%lld", f + i);
        }
        f[n + 1] = gao(n, n + 1);
        for (int i = 1; i <= n + 1; ++i)
            f[i] = (f[i] + f[i - 1]) % p;
        int l, r;
        for (int cas = 1; cas <= m; ++cas) {
            scanf("%d %d", &l, &r);
            printf("%lld\n", (gao(n + 1, r) - gao(n + 1, l - 1) + p) % p);
        }
    }
}

int main() {
    // ios::sync_with_stdio(false);
    // cin.tie(nullptr), cout.tie(nullptr);
    // cout << fixed << setprecision(20);

    RUN();
    return 0;
}