다항식 곱셈
두 다항식 F(x)와 G(x)가 주어졌을 때, H(x) = F(x)G(x)를 계산한다.
NTT를 활용해 점값 표현으로 변환한 후 점별 곱셈을 수행하고, 역변환으로 결과를 얻는다. 시간 복잡도는 O(n log n)이다.
void poly_multiply() {
read(n, m);
FOR(i, 0, n) read(f[i]);
FOR(i, 0, m) read(g[i]);
int sz = 1, bit = 0;
while(sz <= n + m) sz <<= 1, ++bit;
FOR(i, 0, sz) rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << (bit - 1));
ntt(f, sz, 1);
ntt(g, sz, 1);
FOR(i, 0, sz) f[i] = mul(f[i], g[i]);
ntt(f, sz, -1);
FOR(i, 0, n + m) print(f[i]);
}다항식 역원
F(x)G(x) ≡ 1 (mod x^n)을 만족하는 G(x)를 구한다.
상수항 G(x)_0 = F(x)_0^(-1)로 시작하여 배수 확장한다. mod x^⌈n/2⌉의 해 G_0(x)를 이용해:
G(x) ≡ 2G_0(x) - F(x)G_0(x)^2 (mod x^n)
시간 복잡도는 T(n) = T(n/2) + O(n log n) = O(n log n)이다.
int tmp[N];
void poly_inv(int* src, int* dst, int deg) {
if(deg == 1) {
dst[0] = mod_pow(src[0], MOD - 2);
return;
}
poly_inv(src, dst, (deg + 1) >> 1);
int sz = 1, bit = 0;
while(sz < deg << 1) sz <<= 1, ++bit;
FOR(i, 0, sz) rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << (bit - 1));
FOR(i, 0, deg) tmp[i] = src[i];
FOR(i, deg, sz) tmp[i] = 0;
ntt(dst, sz, 1);
ntt(tmp, sz, 1);
FOR(i, 0, sz) dst[i] = mul(dst[i], sub(2, mul(dst[i], tmp[i])));
ntt(dst, sz, -1);
FOR(i, deg, sz) dst[i] = 0;
}다항식 제곱근
G(x)^2 ≡ F(x) (mod x^n)을 만족하는 G(x)를 구한다.
상수항은 F(x)_0의 제곱근이며, 배수 확장 공식은:
G(x) ≡ (G_0(x)/2) + (F(x)/(2G_0(x))) (mod x^n)
시간 복잡도는 O(n log n)이다.
다항식 로그함수와 지수함수
테일러 전개를 통해 다항식에 대한 ln과 exp를 정의한다:
exp(x) = Σ x^k/k!(x의 상수항이 0일 때 수렴)ln(1+x) = Σ (-1)^(k+1) x^k/k(x의 상수항이 1일 때 수렴)
다항식 로그함수
G(x) ≡ ln(F(x)) (mod x^n), 단 F(x)_0 = 1
미분과 적분을 활용: G(x) = ∫(F'(x)/F(x)) dx
int der[N], inv_arr[N];
void poly_ln(int* src, int* dst, int deg) {
int sz = 1, bit = 0;
while(sz < deg << 1) sz <<= 1, ++bit;
FOR(i, 0, sz) rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << (bit - 1));
FOR(i, 0, sz) inv_arr[i] = 0;
poly_inv(src, inv_arr, deg);
FOR(i, 1, deg) der[i - 1] = mul(i, src[i]);
FOR(i, deg - 1, sz) der[i] = 0;
ntt(der, sz, 1);
ntt(inv_arr, sz, 1);
FOR(i, 0, sz) der[i] = mul(der[i], inv_arr[i]);
ntt(der, sz, -1);
FOR(i, 1, deg) dst[i] = mul(der[i - 1], mod_inv[i]);
dst[0] = 0;
}뉴턴 반복법
F(G(x)) ≡ 0 (mod x^n)의 근 G(x)를 구한다.
테일러 전개를 통해: G(x) ≡ G_0(x) - F(G_0(x))/F'(G_0(x)) (mod x^n)
다항식 지수함수
G(x) ≡ exp(F(x)) (mod x^n), 단 F(x)_0 = 0
ln(G(x)) - F(x) = 0의 근으로 변환하여 뉴턴 반복법 적용:
G(x) ≡ G_0(x)(1 - ln(G_0(x)) + F(x)) (mod x^n)
int buf[N];
void poly_exp(int* src, int* dst, int deg) {
if(deg == 1) {
dst[0] = 1;
return;
}
poly_exp(src, dst, (deg + 1) >> 1);
FOR(i, 0, deg) buf[i] = 0;
poly_ln(dst, buf, deg);
FOR(i, 0, deg) buf[i] = sub(src[i], buf[i]);
add(buf[0], 1);
int sz = 1, bit = 0;
while(sz < deg << 1) sz <<= 1, ++bit;
FOR(i, 0, sz) rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << (bit - 1));
FOR(i, deg, sz) buf[i] = 0;
ntt(dst, sz, 1);
ntt(buf, sz, 1);
FOR(i, 0, sz) dst[i] = mul(dst[i], buf[i]);
ntt(dst, sz, -1);
FOR(i, deg, sz) dst[i] = 0;
}다항식 거듭제곱
G(x) ≡ F(x)^k (mod x^n), 단 F(x)_0 = 1
로그-지수 변환: G(x) = exp(k · ln(F(x)))
연속 점값 이동
f(0), f(1), ..., f(n)가 주어졌을 때 f(m), f(m+1), ..., f(m+n)를 계산한다.
라그랑주 보간법과 합성수 분해를 활용한 컨볼루션 최적화:
f(m+x) = Π(m+x-i) · Σ F(i)G(x+n-i)
여기서 F(i) = f(i)/(i!(n-i)!(-1)^(n-i)), G(i) = 1/(m-n+i)
Chirp Z-변환
다항식 F(x)에 대해 F(c^0), F(c^1), ..., F(c^(m-1))를 계산한다.
지수 항 ij를 이항계수로 분해: ij = C(i+j,2) - C(i,2) - C(j,2)
이를 통해 컨볼루션 형태로 변환: F(c^i) = c^(-C(i,2)) · Σ (F_j · c^(-C(j,2))) · c^(C(i+j,2))
임의 모듈러 다항식 곱셈
NTT를 지원하지 않는 모듈러 P에 대해, 세 NTT 소수 998244353, 469762049, 1004535809에서 각각 계산 후 CRT로 복원한다.
struct tri_int {
int v1, v2, v3;
// 연산자 오버로딩...
int crt(int mod) {
ll x = 1LL * P1 * mul_mod2(sub_mod2(v2, v1 % P2), INV1) + v1;
int k = mul_mod3(sub_mod3(v3, x % P3), INV2);
return (x + 1LL * k * (1LL * P1 * P2 % mod)) % mod;
}
};빠른 팩토리얼
n! mod P를 O(√n log n)에 계산한다.
블록 크기 B = √n으로 설정하고, F_d(x) = Π(i=1 to d)(x+i)의 점값 F_d(0), F_d(B), ..., F_d(dB)를 배수 확장으로 계산한다.
스털링 수
제2종 스털링 수 (행)
S(n, i) = Σ(j=0 to i) (-1)^(i-j) · j^n / (j!(i-j)!)
F_j = j^n/j!, G_j = (-1)^j/j!로 설정하여 컨볼루션 수행
제2종 스털링 수 (열)
EGF 접근: (e^x - 1)^k / k!의 계수
제1종 스털링 수 (행)
상승계수 x^(n̄) = Σ S₁(n,i) x^i를 배수 확장으로 계산
x^(2n̄) = x^(n̄) · (x+n)^(n̄), 후자는 점값 이동과 컨볼루션으로 획득
제1종 스털링 수 (열)
EGF 접근: ln(1/(1-x))^k / k!의 계수