다항식 연산 – 학습

1강 FFT 위에 세우는 다항식 대수: 역원과 나눗셈 공식

목표

NTT로 곱셈을 얻었으면, 그 위에 역원, 나눗셈, 나머지, $\log$ , $\exp$ 를 쌓는다. 이들은 형식적 멱급수(formal power series) 위의 뉴턴법으로 모두 $O(n\log n)$ 에 계산된다. 다항식 보간·점화식·조합 항등식의 강력한 일반 도구다.

멱급수 역원 (뉴턴법)

$$A(x)$$ ( $a_0 \ne 0$ ) 의 역원 $$B$$ ( $A B \equiv 1 \pmod{x^n}$ ) 를 구한다. 차수를 두 배씩 늘리는 뉴턴 반복

$B_{2k} \equiv B_k\,(2 - A\,B_k) \pmod{x^{2k}}$

를 쓴다. 이는 $$f(B) = 1/B - A = 0$$ 에 뉴턴법 $B \leftarrow B - f(B)/f'(B)$ 를 적용한 결과다. 각 반복의 곱셈 비용이 직전 비용의 합으로 기하급수 $\sum 2^i = O(n)$ 항이 되어, 전체 $O(n\log n)$ (마지막 NTT가 지배).

정확성 직관

$$B_k$$ 가 $$x^k$$ 까지 정확하면, 위 갱신은 오차의 차수를 두 배로 밀어내 $x^{2k}$ 까지 정확하게 만든다. 이차 수렴(quadratic convergence)이라 $\log n$ 번 반복으로 충분하다.

다항식 나눗셈과 나머지

차수 $$n$$ 의 $$A$$ 를 차수 $$m$$ 의 $$B$$ 로 나눈 몫 $$Q$$ (차수 $$n-m$$ ), 나머지 $$R$$ (차수 $$): \(A = BQ + R$. 계수를 뒤집은 $\mathrm{rev}(P)(x) = x^{\deg P} P(1/x)$ 를 쓰면$

$\mathrm{rev}(A) \equiv \mathrm{rev}(B)\,\mathrm{rev}(Q) \pmod{x^{\,n-m+1}}$

이 되어, $\mathrm{rev}(Q) = \mathrm{rev}(A)\cdot \mathrm{rev}(B)^{-1} \bmod x^{n-m+1}$ 로 $$Q$$ 를 역원 한 번에 구하고, $$R = A - BQ$$ . 전체 $O(n\log n)$ .

$\log$ 와 $\exp$

$$a_0 = 1$$ 인 멱급수에 대해

$\log A = \int \frac{A'}{A}\,dx, \qquad \exp$ 는 다시 뉴턴법 $B \leftarrow B(1 + F - \log B)$ 로 구한다. 미분·적분은 $$O(n)$$ , 역원·곱이 $O(n\log n)$ .

복잡도 요약

연산	비용
곱셈	$O(n\log n)$
역원	$O(n\log n)$
나눗셈/나머지	$O(n\log n)$
$\log$ / $\exp$	$O(n\log n)$
다점 평가/보간	$O(n\log^2 n)$

2강 다항식 역원·나눗셈 구현과 응용 공식

멱급수 역원 (NTT 기반)

multiply 는 NTT 단원의 합성곱 함수를 재사용한다.

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll MOD = 998244353;
ll power(ll a, ll b){ ll r=1;a%=MOD;for(;b;b>>=1,a=a*a%MOD)if(b&1)r=r*a%MOD;return r; }
vector<ll> multiply(vector<ll> a, vector<ll> b);   // NTT 단원에서 가져옴

// A * B ≡ 1 (mod x^n) 인 B 를 반환
vector<ll> inverse(vector<ll> A, int n) {
    vector<ll> B = { power(A[0], MOD - 2) };        // x^1 까지: 1/a0
    int k = 1;
    while (k < n) {
        k <<= 1;
        vector<ll> a(A.begin(), A.begin() + min((int)A.size(), k));
        a.resize(k, 0);
        vector<ll> t = multiply(a, B);              // A*B
        t.resize(k);
        for (auto& x : t) x = (MOD - x) % MOD;
        t[0] = (t[0] + 2) % MOD;                    // 2 - A*B
        B = multiply(B, t);                         // B*(2 - A*B)
        B.resize(k);
    }
    B.resize(n);
    return B;
}

다항식 나눗셈 (몫과 나머지)

// A = B*Q + R 에서 Q, R 반환 (deg A = n, deg B = m)
pair<vector<ll>,vector<ll>> divmod(vector<ll> A, vector<ll> B) {
    int n = A.size() - 1, m = B.size() - 1;
    if (n < m) return {{0}, A};
    vector<ll> ra(A.rbegin(), A.rend()), rb(B.rbegin(), B.rend());
    rb.resize(n - m + 1);
    vector<ll> rq = multiply(ra, inverse(rb, n - m + 1));
    rq.resize(n - m + 1);
    vector<ll> Q(rq.rbegin(), rq.rend());           // 다시 뒤집어 몫
    vector<ll> BQ = multiply(B, Q);
    vector<ll> R(m);
    for (int i = 0; i < m; i++) R[i] = (A[i] - (i < (int)BQ.size() ? BQ[i] : 0) % MOD + MOD) % MOD;
    return {Q, R};
}

자주 하는 실수

$$a_0$$ 가역. 역원은 $a_0\neq 0$ (모듈러 가역) 필요. 상수항이 0이면 시프트로 인수분해 후 처리.
차수 패딩. 뉴턴 반복마다 길이를 $$2k$$ 로 맞추고 마지막에 $$n$$ 으로 자른다.
rev 길이. 나눗셈에서 $\mathrm{rev}(B)$ 를 $$n-m+1$$ 로 잘라야 몫 차수가 맞는다.
모듈러 일관. 모든 연산을 같은 NTT 소수에서. 답 모듈러가 다르면 멀티모듈러 CRT.

응용

문제	도구
선형 점화식 일반항(생성함수)	역원 (분모)
카탈란/분할수 등 조합 수열	$\exp$ , $\log$
다항식 점화 $$N$$ 번째 항	키타마사 + 나눗셈 가속
다점 평가/보간	곱·나머지 트리 $O(n\log^2 n)$

$\exp/\log$ 와 조합론

$$a_0=1$$ 인 생성함수에서 $\exp(\log)$ 항등식은 "연결 성분 ↔ 전체 구조" 같은 지수형 생성함수(EGF) 관계를 계산으로 바꾼다. 집합 분할, 라벨 그래프 수 등은 $\exp$ 한 번으로 떨어진다. 다항식 대수는 이런 조합 항등식을 기계적으로 $O(n\log n)$ 에 평가하는 만능 엔진이다.