온라인 합성곱

문제

다음 형태의 점화식을 생각하자.

$$ f_n = \sum_{k=1}^{n} g_k \, f_{n-k} \quad (n \ge 1),\qquad f_0 = 1. $$

\(f_n\)을 계산하려면 \(f_0, \dots, f_{n-1}\)이 필요하고, 그 자체가 합성곱이다. 게다가 \(g_k\)가 \(f\)에 의존하는(자기 참조) 경우도 흔하다. 예: \(f = \exp(g)\)의 항별 점화, 트리/카탈란류 카운팅.

순진하게 각 \(n\)마다 합을 계산하면 \(O(n^2)\). 온라인(relaxed) 합성곱 은 이를 \(O(n \log^2 n)\)으로 낮춘다 — 단, \(f_n\)을 계산하는 시점에 \(f_{만 사용 한다는 인과(online) 제약을 지키면서.

왜 보통 FFT가 안 되나

보통 FFT 합성곱은 두 완성된 다항식을 곱한다. 하지만 여기선 \(f_n\)을 구할 때 \(f_n\) 자신이 아직 없다(\(g\)가 \(f\)에 의존하면 더더욱). 오프라인으로 전체를 한 번에 곱을 수 없다. 그래서 분할정복 + 부분 기여 누적 이 필요하다.

CDQ 분할정복 아이디어

구간 \([l, r)\)의 \(f\)를 모두 구하는 solve(l, r)을 재귀로 정의한다.

solve(l, r):
    if r - l == 1:
        f[l] 확정(이미 누적된 기여 + 자기 항)
        return
    mid = (l + r) / 2
    solve(l, mid)                       # 왼쪽 먼저 확정
    왼쪽 f[l..mid)가 오른쪽 f[mid..r)에 주는 기여를 FFT로 더함
    solve(mid, r)

핵심: solve(l, mid)로 왼쪽 절반이 확정 된 뒤, 그 값들이 오른쪽 절반에 주는 합성곱 기여를 미리 더해 둔다. 오른쪽으로 내려가기 전에 더하므로 인과율이 지켜진다.

기여 합산의 형태

\(f_n\)(\(n \in [mid, r)\))에 대한 왼쪽 기여는

$$ \sum_{k=l}^{mid-1} g_{n-k}\, f_k \quad\text{또는}\quad \sum f_k\, g_{n-k} $$

형태(점화식에 따라). 이것을 두 배열 \(\{f_k\}_{k \in [l, mid)}\)와 \(\{g_j\}\)의 부분 합성곱으로 보고 NTT 한 번에 처리한다. 단, \(g\)가 \(f\)에 의존하면 \(g\)도 "확정된 범위"만 사용한다(대칭 처리: \(f \times g\)와 \(g \times f\) 양쪽 기여).

복잡도 분석

분할정복 깊이 \(\log n\). 각 깊이에서 모든 구간의 NTT 비용 합이 \(O(n \log n)\). 따라서

$$ T(n) = 2T(n/2) + O(n \log n) = O(n \log^2 n). $$

대안: relaxed (online) 방식

CDQ는 "구간을 미리 안다"는 점에서 반-오프라인이다. 진짜 온라인(한 항씩, 미래 길이 모름)에는 van der Hoeven의 relaxed multiplication 이 있어 같은 \(O(n \log^2 n)\)를 준다. 블록 크기를 2의 거듭제곱으로 쪼개, \(f_n\)이 확정될 때마다 "그 항이 영향을 주는 미래 블록들"에 기여를 예약 적립한다. 경시에서는 보통 구현이 단순한 CDQ를 쓴다.

정리

• 자기 참조 합성곱 점화식 = 온라인 합성곱.
• 인과율을 지키며 FFT를 쓰려면 CDQ 분할정복.
• \(O(n \log^2 n)\). 다음 강의에서 구현.

목표 점화식 예

$$ f_0 = 1,\qquad f_n = \frac{1}{n}\sum_{k=1}^{n} k\, g_k\, f_{n-k}. $$

이는 \(f = \exp(G)\) 류(여기서 \(g\)는 알려진 수열)의 항별 점화다. 일반화하면 \(g\)가 \(f\)에 의존해도 같은 틀이 작동한다.

골격

typedef long long ll;
const ll MOD = 998244353;
int N;
vector<ll> f, g;                  // f: 미정(채워 감), g: 입력(또는 f 의존)
// poly_mul(a, b): NTT 곱

ll invn(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; }

solve(l, r): 핵심 재귀

void solve(int l, int r){
    if(r - l == 1){
        if(l == 0){ f[0] = 1; return; }
        // 이 시점 f[l]에는 누적 기여가 이미 들어 있음 → 정규화
        f[l] = f[l] % MOD * invn(l) % MOD;
        return;
    }
    int mid = (l + r) >> 1;
    solve(l, mid);                          // 왼쪽 확정

    // 왼쪽 f[l..mid)가 오른쪽 f[mid..r)에 주는 기여:
    //   contrib[n] += sum_{k in [l,mid)} (gterm) * f[k],  gterm = (n-k)*g[n-k]
    int lenF = mid - l;
    int lenG = r - l;                        // 필요한 g 구간 길이
    vector<ll> A(lenF), B(lenG, 0);
    for(int k = l; k < mid; k++) A[k - l] = f[k];
    for(int j = 1; j < lenG; j++)            // gterm_j = j * g[j]
        B[j] = (ll)j % MOD * g[j] % MOD;
    vector<ll> C = poly_mul(A, B);           // C[t] = sum A[i]B[j], i+j=t
    // A의 인덱스는 k-l, B의 인덱스는 j=n-k → t = (k-l)+(n-k) = n-l
    for(int n = mid; n < r; n++){
        int t = n - l;
        if(t < (int)C.size()) f[n] = (f[n] + C[t]) % MOD;
    }

    solve(mid, r);                           // 오른쪽 확정
}

호출

vector<ll> relaxedExp(const vector<ll>& gin, int n){  // f = exp(G) 항별
    N = n; f.assign(n, 0); g = gin; g.resize(n, 0);
    solve(0, n);
    return f;                                // f[0..n-1]
}

\(g\)가 \(f\)에 의존하는 경우(자기 참조)

\(g_j\) 자체가 \(f\)로 정의되면, solve(l, mid)가 끝난 직후 그 범위의 \(g\)를 갱신한 뒤 기여를 더한다. 또 대칭 기여(\(g\)의 왼쪽이 \(f\)의 오른쪽에 주는 것, 그 반대)를 모두 처리해야 하므로 두 번의 부분 곱을 더한다. 단, \(l=0\) 블록은 "대각선"이 포함되므로 길이 1까지 내려가 직접 처리(인과율 보존).

// 일반형 f_n = sum_{k} f_k * g_{n-k} (자기참조):
//  - solve(l,mid) 후 f[l..mid) × g[전구간] 기여를 오른쪽에 적립
//  - g가 f로 정의되면 같은 시점에 g[l..mid)도 확정해 둠

복잡도

각 재귀 레벨의 NTT 총비용 \(O(n \log n)\), 레벨 \(\log n\)개 → \(O(n \log^2 n)\). \(n \le 2 \times 10^5\)급에서 실용적.

검증

• \(g\)를 알려진 수열로 두고 결과를 오프라인 poly_exp와 비교(round-trip).
• 카탈란 수 점화(\(C_n = \sum C_k C_{n-1-k}\))를 자기 참조 형태로 구현해 닫힌 형과 대조.
• 작은 \(n\)은 \(O(n^2)\) 브루트포스와 일치 확인.

함정

• 인과율: 오른쪽으로 내려가기 전에 왼쪽 기여를 더한다. 순서가 바뀌면 미래 값을 사용하는 버그.
• 자기 참조 시 대각선 항(같은 블록 내부 \(k+j=n\))은 base case(길이 1)에서만 더해 중복/누락 방지.
• 인덱스 오프셋(\(t = n - l\))을 정확히. NTT 결과 길이 점검.

온라인 합성곱은 "FFT를 인과 점화식에 끼워 넣는" 기술이다. CDQ 분할정복이 가장 구현하기 쉬운 길이다.