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