루비 III문제
차수 \(< n\)인 다항식 \(P(x)\)와 점 \(x_0, \dots, x_{n-1}\)이 주어졌을 때:
- 다중점 평가: 모든 \(P(x_i)\)를 구한다.
- 보간(역연산): 점-값 쌍 \((x_i, y_i)\)에서 \(P\)를 복원한다.
순진하게 하면 평가는 \(O(n^2)\)(호너 \(n\)번), 보간은 라그랑주 \(O(n^2)\). 목표는 둘 다 \(O(n \log^2 n)\).
핵심 도구: subproduct tree
점들로부터 곱-다항식을 분할정복으로 미리 만든다.
$$ Z(x) = \prod_{i=0}^{n-1} (x - x_i). $$
리프는 \((x - x_i)\), 내부 노드는 두 자식의 곱(NTT). 트리 전체를 만드는 비용:
$$ T(n) = 2T(n/2) + O(n \log n) = O(n \log^2 n). $$
각 노드는 자기 구간의 점들에 대한 \(\prod (x - x_j)\)를 저장한다.
다중점 평가: 나머지로 내려가기
핵심 보조정리:
$$ P(x_i) = \big(P \bmod (x - x_i)\big). $$
더 일반적으로, 구간 점들의 곱 \(Z_L = \prod_{i \in L}(x - x_i)\)에 대해
$$ P(x_i) = \big((P \bmod Z_L) \bmod (x - x_i)\big) \quad (i \in L). $$
따라서 루트에서 \(P\)를 들고, 각 단계에서 왼/오른쪽 자식의 곱-다항식으로 다항식 나머지 를 취하며 내려간다. 나머지 연산이 NTT로 \(O(d \log d)\)이므로 전체 \(O(n \log^2 n)\).
eval(node, P):
if leaf: return P(x_node) # P는 상수
P_L = P mod Z[left]
P_R = P mod Z[right]
return eval(left, P_L) ++ eval(right, P_R)
보간: 라그랑주 + 미분
라그랑주 보간:
$$ P(x) = \sum_{i} y_i \prod_{j \ne i} \frac{x - x_j}{x_i - x_j} = \sum_i \frac{y_i}{Z'(x_i)} \cdot \frac{Z(x)}{x - x_i}. $$
여기서 분모 \(\prod_{j\ne i}(x_i - x_j) = Z'(x_i)\)다(곱의 미분, 다른 항들이 0이 되어 남는 것). 따라서:
- \(Z(x) = \prod (x - x_i)\)와 그 도함수 \(Z'(x)\)를 구한다.
- 다중점 평가 로 \(Z'(x_i)\)를 한꺼번에 계산한다.
- \(c_i = y_i / Z'(x_i)\).
- \(\sum_i c_i \cdot \dfrac{Z(x)}{x - x_i}\)를 subproduct tree 위에서 분할정복으로 합친다:
$$ \frac{Z}{x - x_i} = Z_R \cdot \frac{Z_L}{x - x_i} + Z_L \cdot \frac{Z_R}{x - x_i} $$
형태로 자식 결과를 결합(좌/오른쪽 곱을 교차 곱). 전체 \(O(n \log^2 n)\).
복잡도 요약
| 연산 | 순진 | 고속 |
|---|---|---|
| 다중점 평가 | \(O(n^2)\) | \(O(n \log^2 n)\) |
| 보간 | \(O(n^2)\) | \(O(n \log^2 n)\) |
| subproduct tree | — | \(O(n \log^2 n)\) |
다음 강의에서 NTT 위에 다항식 나머지와 트리 구현을 본다.