라그랑주 보간법을 활용한 다항식 값 추정 및 거듭제곱 합 알고리즘

라그랑주 보간법(Lagrange Interpolation)은 평면 위에 주어진 $n$개의 점을 모두 지나는 차수가 가장 낮은 다항식을 구하는 방법입니다. 수치 해석뿐만 아니라 알고리즘 문제 해결에서도 특정 다항식의 값을 예측하거나 거듭제곱의 합을 계산할 때 유용하게 사용됩니다. 라그랑주 보간법의 핵심 공식은 다음과 같습니다. 주어진 $n$개의 점 $(x_0, y_0), (x_1, y_1), \dots, (x_{n-1}, y_{n-1})$에 대해 다항식 $P(x)$는 다음과 같이 정의됩니다. $$P(x) = \sum_{i=0}^{n-1} y_i \prod_{j=0, j \neq i}^{n-1} \frac{x - x_j}{x_i - x_j}$$ 이 공식을 구현하면 $O(n^2)$의 시간 복잡도로 임의의 $x$에 대한 $P(x)$ 값을 구할 수 있습니다.

1. 기본적인 라그랑주 보간법 구현

다음은 모듈러 역원을 이용하여 $n$개의 점이 주어졌을 때 특정 위치의 다항식 값을 구하는 표준적인 구현입니다.
#include <iostream>
#include <vector>

using namespace std;

typedef long long ll;
const int MOD = 998244353;

ll fast_pow(ll base, ll exp) {
    ll res = 1;
    base %= MOD;
    while (exp > 0) {
        if (exp % 2 == 1) res = (res * base) % MOD;
        base = (base * base) % MOD;
        exp /= 2;
    }
    return res;
}

ll get_inverse(ll n) {
    return fast_pow(n, MOD - 2);
}

ll solve_lagrange(int n, ll target_x, const vector<ll>& vx, const vector<ll>& vy) {
    ll total_val = 0;
    for (int i = 0; i < n; ++i) {
        ll numerator = 1;
        ll denominator = 1;
        for (int j = 0; j < n; ++j) {
            if (i == j) continue;
            numerator = numerator * (target_x - vx[j] % MOD + MOD) % MOD;
            denominator = denominator * (vx[i] - vx[j] % MOD + MOD) % MOD;
        }
        ll term = (vy[i] * numerator % MOD) * get_inverse(denominator) % MOD;
        total_val = (total_val + term) % MOD;
    }
    return total_val;
}

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

    int n;
    ll k;
    cin >> n >> k;

    vector<ll> x_points(n), y_points(n);
    for (int i = 0; i < n; ++i) {
        cin >> x_points[i] >> y_points[i];
    }

    cout << solve_lagrange(n, k, x_points, y_points) << endl;

    return 0;
}

2. 거듭제곱의 합과 라그랑주 보간법의 응용

연속된 자연수의 거듭제곱 합 $S_k(n) = \sum_{i=1}^n i^k$는 $n$에 대한 $k+1$차 다항식으로 나타낼 수 있습니다. 이 성질을 이용하면 $k+2$개의 점을 샘플링하여 라그랑주 보간법을 적용함으로써 매우 큰 $n$에 대해서도 $S_k(n)$을 효율적으로 구할 수 있습니다. 특히 특정 조건(예: 특정 원소들을 제외한 합)이 추가된 문제에서는 다항식의 성질을 활용하여 전체 합에서 제외된 부분들을 차감하는 방식으로 접근할 수 있습니다.
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

typedef long long ll;
const int MOD = 1e9 + 7;

ll power_mod(ll b, ll e) {
    ll r = 1;
    while (e) {
        if (e & 1) r = r * b % MOD;
        b = b * b % MOD;
        e >>= 1;
    }
    return r;
}

ll interpolate(int count, ll k, const vector<ll>& vx, const vector<ll>& vy) {
    ll res = 0;
    for (int i = 1; i <= count; ++i) {
        ll up = 1, down = 1;
        for (int j = 1; j <= count; ++j) {
            if (i == j) continue;
            up = up * (k - vx[j] % MOD + MOD) % MOD;
            down = down * (vx[i] - vx[j] % MOD + MOD) % MOD;
        }
        res = (res + vy[i] * up % MOD * power_mod(down, MOD - 2)) % MOD;
    }
    return res;
}

void process_test_case() {
    ll n;
    int m;
    if (!(cin >> n >> m)) return;

    vector<ll> excluded(m + 1, 0);
    for (int i = 1; i <= m; ++i) cin >> excluded[i];
    sort(excluded.begin() + 1, excluded.end());

    int degree = m + 1;
    vector<ll> x(degree + 3), y(degree + 3, 0);
    for (int i = 1; i <= degree + 2; ++i) {
        x[i] = i;
        y[i] = (y[i - 1] + power_mod(i, degree)) % MOD;
    }

    ll total_ans = 0;
    for (int i = 1; i <= m + 1; ++i) {
        ll offset = excluded[i - 1] + 1;
        ll current_n = n - offset + 1;
        
        total_ans = (total_ans + interpolate(degree + 2, current_n, x, y)) % MOD;
        
        for (int j = i; j <= m; ++j) {
            ll val = power_mod(excluded[j] - offset + 1, degree);
            total_ans = (total_ans - val + MOD) % MOD;
        }
    }
    cout << total_ans << "\n";
}

int main() {
    int t;
    cin >> t;
    while (t--) {
        process_test_case();
    }
    return 0;
}
위의 코드는 각 테스트 케이스마다 거듭제곱 합의 다항식 성질을 이용하여 전체 합을 구하고, 문제 조건에 맞게 특정 원소들의 기여분을 제거하는 로직을 담고 있습니다. 라그랑주 보간법을 활용하면 복잡한 수열의 합 공식을 외우지 않고도 점들의 관계만으로 값을 추론할 수 있는 강력한 도구가 됩니다.

태그: LagrangeInterpolation NumberTheory mathematics algorithm CompetitiveProgramming

10월 16일 16:27에 게시됨