Nội suy Lagrange

Wiki › Thuật toán › Toán học

huunguyen · Last updated 8, Tháng 4, 2026, 16:10

Nội suy Lagrange tìm đa thức bậc $\leq N - 1$ qua $N$ điểm $(x_{i}, y_{i})$ và tính giá trị tại điểm bất kỳ trong $O (N^{2})$ (tổng quát) hoặc $O (N)$ (khi $x_{i}$ là dãy liên tiếp).

Ứng dụng: Tính giá trị đa thức tại điểm lớn khi biết một số giá trị đặc biệt, tổng $\sum_{i = 1}^{n} f (i)$ với $f$ là đa thức.

Công thức

Đa thức Lagrange qua $N$ điểm:

P (x) = \sum_{i = 0}^{N - 1} y_{i} \cdot \prod_{j e q i} \frac{x - x_{j}}{x_{i} - x_{j}}

Cài đặt tổng quát — $O (N^{2})$

const long long MOD = 1e9 + 7;

long long power(long long a, long long b, long long mod) {
    long long res = 1; a %= mod;
    for (; b > 0; b >>= 1) { if (b & 1) res = res * a % mod; a = a * a % mod; }
    return res;
}
long long inv(long long a) { return power(a, MOD - 2, MOD); }

// Nội suy tại x từ N điểm (xi[], yi[])
long long lagrange(vector<long long>& xi, vector<long long>& yi, long long x) {
    int n = xi.size();
    long long ans = 0;
    for (int i = 0; i < n; i++) {
        long long num = yi[i], den = 1;
        for (int j = 0; j < n; j++) {
            if (j == i) continue;
            num = num % MOD * ((x - xi[j] % MOD + MOD) % MOD) % MOD;
            den = den % MOD * ((xi[i] - xi[j] % MOD + MOD) % MOD) % MOD;
        }
        ans = (ans + num % MOD * inv(den)) % MOD;
    }
    return ans;
}

Cài đặt nhanh — $O (N)$ khi $x_{i} = 0, 1, 2, \dots, N - 1$

// Nội suy tại x từ N điểm (0, y[0]), (1, y[1]), ..., (N-1, y[N-1])
long long lagrange_consec(vector<long long>& y, long long x) {
    int n = y.size();
    x %= MOD;

    // Tiền xử lý prefix/suffix product và factorial
    vector<long long> pre(n+1, 1), suf(n+1, 1);
    for (int i = 0; i < n; i++) pre[i+1] = pre[i] % MOD * ((x - i % MOD + MOD) % MOD) % MOD;
    for (int i = n-1; i >= 0; i--) suf[i] = suf[i+1] % MOD * ((x - i % MOD + MOD) % MOD) % MOD;

    vector<long long> fact(n, 1), inv_fact(n, 1);
    for (int i = 1; i < n; i++) fact[i] = fact[i-1] * i % MOD;
    inv_fact[n-1] = power(fact[n-1], MOD-2, MOD);
    for (int i = n-2; i >= 0; i--) inv_fact[i] = inv_fact[i+1] * (i+1) % MOD;

    long long ans = 0;
    for (int i = 0; i < n; i++) {
        long long num = pre[i] % MOD * suf[i+1] % MOD;
        long long den = inv_fact[i] % MOD * inv_fact[n-1-i] % MOD;
        if ((n-1-i) % 2 == 1) den = MOD - den;
        ans = (ans + y[i] % MOD * num % MOD * den) % MOD;
    }
    return ans;
}

Ứng dụng: Tổng lũy thừa $\sum_{i = 1}^{n} i^{k}$

$S (n) = \sum_{i = 1}^{n} i^{k}$ là đa thức bậc $k + 1$ theo $n$ . Tính $S (1), S (2), \dots, S (k + 2)$ rồi nội suy tại $n$ :

long long sum_of_powers(long long n, int k) {
    int pts = k + 2;
    vector<long long> y(pts);
    long long cur = 0, pw = 1;
    for (int i = 1; i <= pts; i++) {
        pw = pw * i % MOD;   // i^k... cần power(i, k, MOD)
        cur = (cur + power(i, k, MOD)) % MOD;
        y[i-1] = cur;
    }
    if (n < pts) return y[n-1];
    // Nội suy tại n với xi = 1,2,...,pts
    // Dùng lagrange_consec với shift: y[i] tại x = i+1
    // ...
    return lagrange_consec(y, n % MOD);   // cần điều chỉnh offset
}

Ứng dụng: Giá trị đa thức DP tại $n$ lớn

Khi $d p [i]$ là đa thức bậc $K$ theo $i$ , tính $d p [n]$ với $n$ lớn bằng cách:

Tính $d p [0], d p [1], \dots, d p [K + 1]$ bằng DP thông thường.
Nội suy Lagrange tại $n$ .

Độ phức tạp

Phương pháp	Độ phức tạp
Tổng quát ( $N$ điểm bất kỳ)	$O (N^{2})$
$x_{i}$ liên tiếp	$O (N)$ (sau $O (N)$ tiền xử lý)

Khi nào dùng Nội suy Lagrange?

$n \leq 10^{18}$ nhưng đa thức bậc thấp ( $K \leq 10^{6}$ ).
Tổng $\sum i^{k}$ hoặc $\sum f (i)$ với $f$ là đa thức.
DP có giá trị là đa thức theo một tham số.

Bình luận

Không có bình luận tại thời điểm này.