← 다이아몬드 V

고속 푸리에 변환

다항식 곱셈을 O(N log N)에 — FFT와 NTT.

수학

다이아몬드 V

선수 지식: 분할 정복

1강 다항식 곱셈과 FFT의 원리 공식

다항식 곱셈이라는 문제

두 다항식 $A(x)=\sum_{i=0}^{n-1} a_i x^i$ , $B(x)=\sum_{j=0}^{m-1} b_j x^j$ 의 곱 $C=A\cdot B$ 를 구하면,

$c_k = \sum_{i+j=k} a_i b_j$

가 된다. 정의대로 계산하면 $$O(nm)$$ 이지만, 이는 곧 길이 $$n,m$$ 인 두 수열의 합성곱(convolution) 이다. 큰 정수 곱셈, 문자열 매칭 점수, 부분합 개수 세기 등이 전부 이 형태로 환원된다.

점-값 표현과 핵심 통찰

차수 $$d$$ 미만의 다항식은 서로 다른 점 $$d$$ 개의 함숫값으로 유일하게 결정된다. 따라서

$$A,B$$ 를 같은 점 $$N$$ 개에서 평가하고 ( $N \ge n+m-1$ ),
점마다 값을 곱한 뒤 ( $$O(N)$$ ),
다시 계수로 보간하면

곱을 얻는다. 문제는 평가/보간이 일반적으로 $$O(N^2)$$ 라는 점이다. FFT의 통찰은 평가점으로 $$N$$ 제곱근(단위근)을 쓰면 분할 정복이 가능하다는 것이다.

단위근과 분할 정복

$\omega_N = e^{2\pi i / N}$ 를 $$N$$ 차 원시 단위근이라 하자. $$A$$ 를 짝/홀 차수로 나누면

$A(x) = A_{\text{even}}(x^2) + x\,A_{\text{odd}}(x^2)$

$x = \omega_N^k$ 를 대입하면 $x^2 = \omega_{N/2}^k$ 가 되어, 크기 $$N$$ 평가가 크기 $$N/2$$ 짜리 두 평가로 줄어든다. 또한 $\omega_N^{k+N/2} = -\omega_N^k$ 이므로 한 번의 계산으로 두 출력을 얻는다 (butterfly):

$X_k = E_k + \omega_N^k O_k,\qquad X_{k+N/2} = E_k - \omega_N^k O_k$

점화식 $$T(N)=2T(N/2)+O(N)$$ 이므로 전체 $O(N\log N)$ .

역변환

DFT 행렬은 $F_{jk}=\omega_N^{jk}$ 이고 그 역은 $F^{-1}_{jk} = \frac{1}{N}\omega_N^{-jk}$ 이다. 즉 역FFT는 $\omega_N$ 대신 $\omega_N^{-1}$ 을 쓰고 마지막에 $$N$$ 으로 나누면 된다. 정변환과 코드를 공유할 수 있다.

정밀도와 NTT의 동기

복소수 FFT는 부동소수점 오차가 있어, 계수가 큰 정수 합성곱에서는 반올림이 위험하다. 모듈러 환경에서 정확한 정수 결과가 필요하면 단위근을 소수 $$p$$ 의 곱셈군에서 잡는 NTT(수론적 변환)를 쓴다. $p = c\cdot 2^k + 1$ 꼴(예: $998244353 = 119\cdot 2^{23}+1$ )이면 $$2^k$$ 차 원시근이 존재해 같은 butterfly가 정수 위에서 정확히 돈다.

복잡도 요약

연산	복잡도
직접 곱셈	$$O(nm)$$
FFT/NTT 곱셈	$O(N\log N)$ , $N=2^{\lceil\log_2(n+m-1)\rceil}$
메모리	$$O(N)$$

2강 NTT 구현과 실전 사용법 공식

반복형 NTT 구현

재귀 대신 비트 반전 정렬 후 반복(iterative)으로 구현하면 상수가 작다. 모듈러 $$998244353$$ , 원시근 $$g=3$$ 을 쓴다.

#include <bits/stdc++.h>
using namespace std;
const long long MOD = 998244353, G = 3;

long long power(long long a, long long b, long long m) {
    long long r = 1; a %= m;
    for (; b; b >>= 1, a = a * a % m)
        if (b & 1) r = r * a % m;
    return r;
}

void ntt(vector<long long>& a, bool inv) {
    int n = a.size();
    for (int i = 1, j = 0; i < n; i++) {       // 비트 반전 정렬
        int bit = n >> 1;
        for (; j & bit; bit >>= 1) j ^= bit;
        j ^= bit;
        if (i < j) swap(a[i], a[j]);
    }
    for (int len = 2; len <= n; len <<= 1) {
        long long w = power(G, (MOD - 1) / len, MOD); // len차 원시근
        if (inv) w = power(w, MOD - 2, MOD);
        for (int i = 0; i < n; i += len) {
            long long wn = 1;
            for (int k = 0; k < len / 2; k++) {
                long long u = a[i + k];
                long long v = a[i + k + len / 2] * wn % MOD;
                a[i + k] = (u + v) % MOD;
                a[i + k + len / 2] = (u - v + MOD) % MOD;
                wn = wn * w % MOD;
            }
        }
    }
    if (inv) {
        long long ninv = power(n, MOD - 2, MOD);
        for (auto& x : a) x = x * ninv % MOD;
    }
}

vector<long long> multiply(vector<long long> a, vector<long long> b) {
    int need = a.size() + b.size() - 1, n = 1;
    while (n < need) 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);
    a.resize(need);
    return a;
}

자주 하는 실수

크기를 2의 거듭제곱으로 올리지 않음. butterfly 분할이 깨진다. 항상 $$n+m-1$$ 이상인 최소 $$2^k$$ 로 패딩한다.
inv에서 $$N$$ 으로 안 나눔. 역변환은 모듈러 역원 곱이 필요하다.
모듈러 일치. 답 모듈러가 NTT 소수와 다르면, 두세 개의 NTT 소수로 돌린 뒤 CRT로 합쳐 큰 값을 복원해야 한다 (계수 곱이 $$998244353$$ 을 넘는 경우).
음수 계수. 입력을 미리 $$[0,MOD)$$ 로 정규화한다.

임의 모듈러 합성곱 (큰 계수)

답이 임의 모듈러 $$M$$ 이고 계수가 커서 단일 NTT 소수로 부족하면, 서로소인 NTT 소수 세 개로 곱한 뒤 CRT(Garner)로 진짜 정수를 복원하고 마지막에 $\bmod\,M$ 한다. 보통 $p_1=998244353,\ p_2=985661441,\ p_3=754974721$ 을 쓴다.

고전 응용

문제	환원 형태
큰 정수 곱셈	자릿수 합성곱 후 carry
문자열 와일드카드 매칭	$\sum (a_i-b_j)^2 a_i b_j$ 형 점수
부분합 가짓수	카운트 벡터의 거듭 합성곱
다항식 역원/ $\log$ / $\exp$	NTT 기반 뉴턴법 (다음 단원)

복잡도

길이 $$n,m$$ 의 합성곱이 $O((n+m)\log(n+m))$ . 멀티 모듈러 CRT 버전은 NTT를 세 번 돌려 상수만 커질 뿐 차수는 동일하다.

연산	복잡도
직접 곱셈	$\(O(nm)\)$
FFT/NTT 곱셈	$O(N\log N)$ , $N=2^{\lceil\log_2(n+m-1)\rceil}$
메모리	$\(O(N)\)$