다항식 로그와 지수 – 학습

1강 뉴턴법으로 다항식 ln과 exp 공식

형식 멱급수의 해석 연산

법 $$x^n$$ 아래에서 다항식(형식 멱급수)에 대해 다음을 $O(n \log n)$ 에 계산한다.

$\ln A(x)$ (단, $$A(0) = 1$$ )
$\exp A(x)$ (단, $$A(0) = 0$$ )
$$A(x)^k$$ , $\sqrt{A(x)}$ 등 파생 연산

모든 것의 토대는 다항식 역원 $A^{-1} \bmod x^n$ 이고, 그 위에 뉴턴 반복 을 얹는다.

뉴턴 반복의 원리

근사해 $B_t \equiv$ (정답) $\bmod x^{2^t}$ 가 있을 때, 한 번의 갱신으로 정밀도를 두 배( $x^{2^{t+1}}$ )로 올린다. 방정식 $$F(B) = 0$$ 을 풀 때:

$B_{t+1} = B_t - \frac{F(B_t)}{F'(B_t)} \pmod{x^{2^{t+1}}}.$

형식 멱급수에서도 같은 공식이 성립하며, 정밀도가 매 단계 두 배가 되어 총비용은 마지막 곱의 비용이 지배해 $O(n \log n)$ .

역원: $$F(B) = 1/B - A$$

B_{t+1} = B_t (2 - A B_t)  (mod x^{2^{t+1}})

$A(0) \ne 0$ 필요. 초기값 $B_0 = A(0)^{-1}$ .

로그: 적분으로 환원

$$A(0) = 1$$ 일 때, $\ln A$ 의 미분이 핵심이다.

$\frac{d}{dx}\ln A = \frac{A'}{A} \;\Rightarrow\; \ln A = \int \frac{A'(x)}{A(x)}\, dx.$

따라서:

$$A'$$ 를 계산(계수 $a_k \to k a_k$ ).
$A^{-1} \bmod x^{n}$ 를 뉴턴법으로.
$A' \cdot A^{-1}$ (NTT 곱).
항별 적분( $c_k \to c_{k-1}/k$ ). 상수항은 $\ln A(0) = \ln 1 = 0$ .

뉴턴 없이 역원만으로 끝난다. $O(n \log n)$ .

지수: $F(B) = \ln B - A$

$$A(0) = 0$$ 일 때 $\exp A$ 를 뉴턴법으로. $F(B) = \ln B - A$ , $$F'(B) = 1/B$$ 이므로

$B_{t+1} = B_t \big(1 - \ln B_t + A\big) \pmod{x^{2^{t+1}}}.$

매 단계 내부에서 $\ln B_t$ 를 계산해야 하므로 로그(=역원)가 필요하다. 초기값 $$B_0 = 1$$ . 정밀도 두 배씩, 총 $O(n \log n)$ .

거듭제곱과 제곱근

$A^k = \exp(k \ln A)$ (단 $$A(0)=1$$ ; 일반은 최저차 항을 빼낸 뒤 처리).
$\sqrt A$ : $$F(B) = B^2 - A$$ , $B_{t+1} = \tfrac12(B_t + A B_t^{-1})$ . $$A(0)$$ 의 modular 제곱근 필요.

정밀도 두 배의 직관 (오차 분석)

$$B_t$$ 의 오차가 $O(x^{2^t})$ 이면, 뉴턴 갱신은 그 오차를 제곱 한다: $O(x^{2^{t+1}})$ . 이것이 차수의 두 배 증가를 보장한다. 형식 멱급수에서는 "오차"가 곧 "최저 비영 차수"이고, 곱셈이 차수를 더하므로 제곱 = 두 배.

정리

토대 = 다항식 역원(뉴턴).
ln = 적분(A'/A), exp = 뉴턴(ln 내부 호출).
pow/sqrt = exp·ln 또는 직접 뉴턴.
전부 $O(n \log n)$ . 다음 강의에서 구현.

2강 구현: ln, exp, pow 공식

전제

NTT 소수 $$p = 998244353$$ , ntt, poly_mul이 있다고 하자. 모든 연산은 법 $$x^n$$ , 계수는 $\bmod p$ .

미분과 적분

typedef long long ll;
const ll MOD = 998244353;
ll inv(ll a){ ll r=1,e=MOD-2; a%=MOD; while(e){if(e&1)r=r*a%MOD;a=a*a%MOD;e>>=1;} return r; }

vector<ll> deriv(vector<ll> a){
    for(int i=1;i<(int)a.size();i++) a[i-1]=a[i]*i%MOD;
    if(!a.empty()) a.pop_back();
    return a;
}
vector<ll> integ(vector<ll> a){           // 상수항 0
    a.push_back(0);
    for(int i=a.size()-1;i>=1;i--) a[i]=a[i-1]*inv(i)%MOD;
    a[0]=0;
    return a;
}

다항식 역원 (뉴턴)

vector<ll> poly_inv(const vector<ll>& A, int n){
    vector<ll> B = { inv(A[0]) };          // B_0 = A(0)^{-1}
    for(int k=1; k<n; k<<=1){
        int m = k<<1;
        vector<ll> a(A.begin(), A.begin()+min((int)A.size(), m));
        a.resize(m);
        vector<ll> t = poly_mul(a, B);     // A B_t
        t.resize(m);
        for(auto&v:t) v=(MOD-v)%MOD;
        t[0]=(t[0]+2)%MOD;                 // 2 - A B_t
        B = poly_mul(B, t);
        B.resize(m);
    }
    B.resize(n);
    return B;
}

로그: $\int A'/A$

vector<ll> poly_ln(vector<ll> A, int n){   // A[0] == 1 필요
    vector<ll> d = deriv(A);
    vector<ll> iv = poly_inv(A, n);
    vector<ll> r = poly_mul(d, iv);
    r.resize(n-1);
    r = integ(r);                          // 상수항 0
    r.resize(n);
    return r;
}

지수: 뉴턴 (내부에 ln)

vector<ll> poly_exp(const vector<ll>& A, int n){  // A[0] == 0 필요
    vector<ll> B = { 1 };                  // B_0 = 1
    for(int k=1; k<n; k<<=1){
        int m = k<<1;
        vector<ll> lnB = poly_ln(B, m);    // ln B_t (mod x^m)
        vector<ll> t(m, 0);
        for(int i=0;i<m;i++){
            ll ai = (i<(int)A.size()? A[i]:0);
            t[i] = ( (i<(int)lnB.size()? (MOD-lnB[i])%MOD : 0) + ai ) % MOD;
        }
        t[0] = (t[0]+1)%MOD;               // 1 - ln B_t + A
        B = poly_mul(B, t);
        B.resize(m);
    }
    B.resize(n);
    return B;
}

거듭제곱: $A^k = \exp(k \ln A)$

vector<ll> poly_pow(vector<ll> A, ll k, int n){
    // 최저 비영 차수 처리
    int lead=0; while(lead<(int)A.size() && A[lead]==0) lead++;
    vector<ll> res(n,0);
    if(lead==(int)A.size()){ res[0]=(k==0); return res; } // A=0
    if((__int128)lead*k >= n){ if(k==0) res[0]=1; return res; }
    ll a0 = A[lead];
    vector<ll> shifted(A.begin()+lead, A.end());
    ll ia0 = inv(a0);
    for(auto&v:shifted) v=v*ia0%MOD;       // 상수항을 1로 정규화
    shifted.resize(n);
    vector<ll> lg = poly_ln(shifted, n);
    ll kmod = ((k%MOD)+MOD)%MOD;
    for(auto&v:lg) v=v*kmod%MOD;
    vector<ll> ex = poly_exp(lg, n);
    ll coef = 1, base=a0%MOD, e=k;          // a0^k
    while(e){ if(e&1) coef=coef*base%MOD; base=base*base%MOD; e>>=1; }
    int sh = (int)(lead*k);                 // x^{lead*k} 만큼 이동
    for(int i=0;i+sh<n && i<(int)ex.size();i++)
        res[i+sh]=ex[i]*coef%MOD;
    return res;
}

검증

poly_exp(poly_ln(A)) == A (단 A[0]=1) round-trip.
$$(1+x)^k$$ 를 poly_pow로 → 이항계수와 비교.
카탈란/벨 수 등 EGF 변환으로 교차 검증.

함정

ln은 A[0]==1, exp는 A[0]==0 전제. 위반 시 정규화 필요.
매 뉴턴 단계의 resize(m) 누락은 흔한 버그.
pow에서 lead*k가 $$n$$ 넘으면 결과는 0(이동만으로 범위 밖).

모든 연산 $O(n \log n)$ . $n \le 10^5 \sim 10^6$ 급 다항식에 실용적이다.