Generating Function

Generating Function, 생성 함수, Formal Power Series, OGF, EGF

정의

Generating Function (생성 함수) 은 수열 (a_0, a_1, a_2, ...) 를 형식 멱급수 (formal power series) A(x) = Σ a_n x^n 으로 인코딩한 것. 수열의 산수 를 다항식 / 멱급수의 대수 로 변환.

PS 에서는 카운팅 DP 를 다항식 곱 / exp / log / 합성으로 표현 → FFT 로 O(N log N) 가속 이라는 패턴이 정형.

문제 상황과 동기

수열을 다항식 또는 멱급수로 인코딩하면 컨볼루션 형태의 DP 를 다항식 곱으로, 점화식을 다항식 exp / log 같은 대수 연산으로 O(N log N) 에 가속할 수 있다.

예를 들어, dp[i] = Σ_j dp[j] · cost[i-j] 꼴의 전이는 순진하게 O(N²) 이지만, 생성 함수 D(x) = Σ dp[i] x^i, C(x) = Σ cost[i] x^i 를 만들면 D(x) = D(x) · C(x) + 1 같은 대수 방정식이 되어 NTT 로 O(N log N) 에 풀린다. 점화식에 a_n = Σ_k a_k · a_{n-k} 처럼 자기 자신과의 곱 형태가 보이면 생성 함수의 exp / log / 역원 연산으로 한방에 정리할 수 있다.

PS 에서는 카운팅 DP 의 전형적인 O(N²) 전이를 O(N log N) 으로 떨어뜨리는 도구로 등장한다. Catalan 수, Bell 수, Stirling 수 같은 조합 수열도 모두 생성 함수의 폐쇄형 또는 대수 조작으로 O(N log N) 에 계산 가능.

시각화

두 가지 표준 GF

OGF (Ordinary Generating Function)

A(x) = Σ a_n x^n. 부분 / 무순서 카운팅 에 자연스러움.

EGF (Exponential Generating Function)

Â(x) = Σ a_n x^n / n!. 순서 있는 배치 / 라벨링 에 자연스러움.

순서 있는 결합 두 종류:
    Â · B̂ = Σ_{k} (n choose k) a_k b_{n-k} x^n / n!

자주 쓰이는 GF

수열	OGF	EGF
1, 1, 1, …	1 / (1 - x)	e^x
1, 2, 4, … (2^n)	1 / (1 - 2x)	e^{2x}
n!	-	1 / (1 - x) (EGF)
C(n, k) (k 고정)	x^k / (1-x)^{k+1}	-
Catalan 수	(1 - √(1 - 4x)) / (2x)	-

표준 연산

1. 곱셈 = 컨볼루션

(A·B)_n = Σ a_k b_{n-k}. FFT 로 O(N log N).

2. 역원 (Inverse)

B = 1/A. 상수항이 0 이 아니면 Newton iteration 으로 O(N log N).

3. exp / log

exp(A) = Σ A^k / k!, log(A) = .... Newton iteration 으로 O(N log N).

4. 합성

B(A(x)). 일반적으로 O(N²), 특수 케이스에서 O(N log N).

응용

1. 동전 / 분할 카운팅

각 동전 종류를 1 + x^c + x^{2c} + ... = 1 / (1 - x^c) 로 → 동전 조합 카운팅.

2. 순서 있는 배치

EGF 곱 = 라벨링된 객체의 결합.

3. 폐쇄형 점화식

GF 가 유리식 으로 정리되면 점화식의 폐쇄형 풀이 (Catalan, Fibonacci 등).

4. 다항 계수

(1+x)^N 의 x^k 계수 = C(N, k). 일반 다항 계수도 유사.

5. 우표 구매하기 / 카운팅 DP

DP 전이가 컨볼루션 형태 → GF 의 곱으로 O(N log N).

함정

1. 형식 vs 해석

생성 함수는 형식적 (formal) 객체. 수렴성 / 정의역은 보통 무시. 단, 해석적 계산 (적분 / 미분 같은) 을 시도할 땐 주의.

2. EGF vs OGF 혼동

곱이 다른 의미 (라벨링 vs 무라벨링). 문제 모델에 맞춰 선택.

3. mod 환경

NTT prime 위에서 작업. 998244353 표준.

4. Newton iteration 의 상수항

exp(A) 는 A(0) = 0 가정. log(A) 는 A(0) = 1 가정. 위반 시 미정의.

구현

다항식 역원, exp, log 의 기본 스켈레톤을 NTT 기반으로 작성. 998244353 mod 환경. 실전에서는 검증된 라이브러리 권장.

// O(N log N) per operation. mod = 998244353 (NTT prime).
#include <vector>
#include <algorithm>
using namespace std;
typedef long long ll;

const ll MOD = 998244353;

// NTT 라이브러리 (생략, assume ntt(a, inv=false/true) exists)
void ntt(vector<ll>& a, bool inv);

// 다항식 곱셈 O(N log N)
vector<ll> poly_mul(vector<ll> a, vector<ll> b) {
    int n = 1;
    while (n < (int)a.size() + (int)b.size() - 1) n <<= 1;
    a.resize(n); b.resize(n);
    ntt(a, false); ntt(b, false);
    for (int i = 0; i < n; i++) a[i] = a[i] * b[i] % MOD;
    ntt(a, true);
    return a;
}

// 다항식 역원: B = 1/A (mod x^n). A[0] != 0 가정.
// Newton iteration: B_{k+1} = B_k (2 - A B_k).
vector<ll> poly_inv(vector<ll> a, int n) {
    vector<ll> b = {1}; // 초기 B_0 = 1 / A[0]
    ll inv0 = 1; // mod_pow(a[0], MOD - 2, MOD) 로 계산
    b[0] = inv0;
    
    for (int k = 1; k < n; k <<= 1) {
        vector<ll> ab = poly_mul(a, b);
        ab.resize(2 * k);
        // 2 - AB
        for (int i = 0; i < 2 * k; i++) ab[i] = (2 - ab[i] + MOD) % MOD;
        b = poly_mul(b, ab);
        b.resize(2 * k);
    }
    b.resize(n);
    return b;
}

// 다항식 exp: B = exp(A). A[0] = 0 가정.
// Newton: B_{k+1} = B_k (1 + A - log(B_k)).
vector<ll> poly_exp(vector<ll> a, int n) {
    // Pseudocode skeleton (full implementation 는 log 와 상호 의존)
    vector<ll> b = {1}; // exp(0) = 1
    for (int k = 1; k < n; k <<= 1) {
        // b_next = b * (1 + a - poly_log(b, 2k))
        // ... (생략)
    }
    b.resize(n);
    return b;
}

// 다항식 log: B = log(A). A[0] = 1 가정.
// log(A) = ∫ A' / A.
vector<ll> poly_log(vector<ll> a, int n) {
    // A' / A 를 적분
    vector<ll> da(n);
    for (int i = 1; i < n; i++) da[i - 1] = a[i] * i % MOD;
    vector<ll> inv_a = poly_inv(a, n);
    vector<ll> frac = poly_mul(da, inv_a);
    frac.resize(n);
    // 적분: frac[i] / (i + 1)
    vector<ll> res(n);
    res[0] = 0;
    for (int i = 1; i < n; i++) {
        ll inv_i = 1; // mod_pow(i, MOD - 2, MOD)
        res[i] = frac[i - 1] * inv_i % MOD;
    }
    return res;
}

구현 팁

1. NTT 기반: 998244353 mod 에서 primitive root = 3. FFT 보다 빠르고 정확.
2. Newton iteration: 반복 깊이 log N. 각 단계에서 크기를 2 배로.
3. 상수항 조건: exp / log 전에 반드시 A[0] = 0 / 1 검증.
4. 검증: 작은 예제 (Fibonacci 수열 생성 함수 등) 로 정합성 확인.

BOJ 연습 문제

번호	제목	링크
BOJ 16725	다항 계수	kokoa-lab
BOJ 13542	우표 구매하기 (Hard)	kokoa-lab
BOJ 26037	지수 · 로그와 테일러 다항식 (Large)	kokoa-lab
BOJ 18248	제야의 종	kokoa-lab

참고

• FFT 와 NTT
• Polynomial Division / Kitamasa
• Mobius Function
• Berlekamp-Massey
• LGV Theorem