📝 상세 정리 # FFT를 잘 모른다면, 먼저 읽고 오자. 다항식의 곱셈 결과를 특정 소수 $p$로 나눈 나머지를 구해야하거나, 값이 커지거나 해서 실수 오차가 발생하는 경우가 있다. 실수를 안쓰고 FFT를 할 수는 없을까? 우리가 FFT에서 핵심으로 사용하던 $\omega = \exp\left(-i\dfrac{2\pi}{N}\right)$를 조금 더 생각해보자. FFT에서 사용되는 핵심적인 성질은 $\omega^N = 1$ 이고, $1, \omega, \omega^2, \cdots, \omega^{N-1}$이 모두 다르다는 점이다. 그러면 모듈러 합동식의 관점에서, 어떤 수 $k$와 어떤 소수 $p$가 있어서 $k^N \equiv 1 \pmod p$를 만족시키고, $1, g, g^2, \cdots, g^{N-1} \pmod p$이 모두 다르다면, FFT와 같은 느낌으로 사용할 수 있지 않을까? 이러한 수 $g$를 원시근이라고 한다. 그러면 $N$을 또 잘 잡아야할 것 같은데, 페르마의 소정리를 이용할 수 있을 것 같다. $a^{p-1} \equiv 1 \pmod p$ 이므로, $N = p-1$이면 좋을 것 같다. FFT를 반으로 쪼개던 방법을 잘 이용하기 위해선, $N$이 $2$로 충분히 많이 나누어 떨어지면 좋겠다. $N = a \times 2^b$ 꼴이면 좋겠고, 이에 따라 $p = a \times 2^b + 1$ 이면 좋겠다. $N$을 $2$로 나누어 떨어지게 할 수 있는 횟수에 따라 FFT로 계산 가능한 배열의 크기가 달라진다! $n \leq 2^b$ 의 크기의 다항식까지만 가능하다. 이로 어울리는 대표적인 소수로는 $p = 998244353 = 119 \times 2^{23} + 1$ 이 있겠다. 이때 원시근 $g = 3$ 을 사용할 수 있다. 그러면 이제 $\omega = \exp\left(-i\dfrac{2\pi}{N}\right)$ 대신 $\omega = g^{(p-1)/n}$ 을 이용해서 FFT를 수행할 수 있게 되었다. 이를 구현하면 다음과 같다. void ntt(vector<mint> &a, bool inv = false){ int N = a.size(); assert(N > 0 && (N & (N-1)) == 0); // N은 2의 거듭제곱이어야 함 // 비트 뒤집기 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]); } // 단위근 미리 계산 mint ang = mint(3).pow((MOD-1)/N); if(inv) ang = ang.inv(); vector<mint> w(N/2); // 단위근 w[0] = 1; rep(i, 1, N/2) w[i] = w[i-1] * ang; // Cooley-Tukey FFT for(int len = 2; len <= N; len <<= 1){ int step = N / len; for(int i = 0; i < N; i += len){ rep(j, 0, len>>1){ mint even = a[i+j], odd = a[i+j+(len>>1)] * w[j*step]; a[i+j] = even + odd; a[i+j+(len>>1)] = even - odd; } } } // 역 FFT인 경우 결과를 N으로 나눔 if(inv){ mint invN = mint(N).inv(); rep(i, 0, N) a[i] *= invN; } } ❔질문 사항 # 🔗 참고 자료 # https://rkm0959.tistory.com/187 https://algoshitpo.github.io/2020/05/20/fft-ntt/
📝 상세 정리 # 이제 슬슬 FFT를 이해할 때가 된것 같다. 정리해보자. 푸리에 변환 # 여러 사인파 / 코사인파가 더해진 함수 $h(t)$가 있다. 일단 먼저 사인파만 있다고 가정해보자. 우리는 이 함수 $h(t)$에서 어떤 주파수를 가진 성분들이 있는지 검사하고싶다. 더 쉽게, 먼저 사인파 하나에 대해서 생각해보자. 함수 $f(x) = \sin{ax}$가 있다. 우리는 $a$를 모른다고 가정하자. 어떻게 하면 이 $a$를 알아낼 수 있을까? 임의의 사인파 $g(x) = \sin{bx}$를 곱해보자. 삼각함수의 곱셈정리에 의해 $f(x)g(x) = \sin{ax}\sin{bx} = \frac{\cos{((a-b)x)} - \cos{((a+b)x)}}{2}$ 위와 같이 나타낼 수 있다. 이를 음의 무한대부터 양의 무한대까지 적분하면, 주기함수의 특성을 이용해서 $a, b$가 같은지 다른지 알아낼 수 있다. $a, b$는 주파수기에 $a, b > 0$이 보장된다. $a = b$일 때만 양의 무한대로 발산하고, 그 외의 경우 진동발산한다. 위의 특징은 여러 사인파의 합 $h(t)$에 대해서도 간단하게 성립한다. 코사인 파가 섞여있다면 코사인파를 곱해서 같은 방법으로 수행해주면 되겠다. 이 때, 오일러 공식 $e^{ix} = \cos{x} + i\sin{x}$을 이용해서 실수부 / 허수부로 나눠서 더 쉽게 계산할 수도 있다. 이를 식으로 나타내면 다음과 같다. $$\hat{h}(x) = \int_{-\infty}^{\infty}{h(t)e^{-2\pi itx}dt}$$ 이는 신호 -> 주파수로의 변환으로 해석하면 된다. 반대로 주파수 -> 신호의 변환도 가능하다. $$h(t) = \int_{-\infty}^{\infty}{\hat{h}(x)e^{2\pi itx}dx}$$ 이를 푸리에 역변환이라고 하자. 여기서 갖고 놀아보자. 이해할때 클로드가 만들어줬다. 신호 종류: 유한 사인파 (현실적) 두 주파수 합성 구형파 무한 사인파 (이상적) ① 시간 도메인 — h(t)
📝 상세 정리 # $2^N$개의 정수 배열 $A$가 주어진다. 이때 $\forall x$ 에 대해 $F(x)$를 $\sum\limits_{i \subseteq x}{A[i]}$ 라고 정의하자. 이는 $x\&i = i$ 인 $i$들에 대해 $A[i]$의 합을 의미한다. 위와 같은 문제를 어떻게 풀 수있을까? 브루트포스 # 느리지만, 다음과 같은 브루트포스로 계산할 수 있겠다. for(int mask = 0; mask < (1<<N); mask++){ for(int i = 0; i < (1<<N); i++){ if((mask&i) == i){ F[mask] += A[i]; } } } 위 식을 그대로 옮긴 것에 가깝다. 시간복잡도는 ${(2^N)}^2 = 4^N$이다. 조금 더 나은 풀이 # 두번째 반복문에 대해, 바깥쪽 반복문에서 켜지지 않은 비트에 대해서도 반복을 도는것은 너무 아깝다. 따라서 다음과 같이도 한번 시도해볼 수 있겠다. for(int mask = 0; mask < (1<<N); mask++){ F[mask] = A[0]; for(int i = 0; i < (1<<N); i = (i-1)&mask) F[mask] += A[i]; } 시간복잡도 증명이 어려워보인다. 이는 $\sum\limits_{k = 0}^N{\binom{N}{K}2^K} = 3^N$ 이라고 한다. Sum over Subsets DP # 위의 방식에서 병목은 어디에서 나타날까? 어떤 $x$의 비트가 $K$개가 꺼져있을 때, $A[x]$는 $2^K$개의 마스크에 의해 방문된다. 이 반복적인 재계산을 줄여야한다. S(mask, i) 정의 # 위 병목을 피하기 위해 새로운 상태를 하나 정의해보자. $S(mask, i)$는 $mask$의 부분집합들 중, $mask$와 하위(오른쪽) $i$개 비트(0~i-1번 인덱스)에서만 다른 것을 의미한다. 예를 들어, $S(110, 2) = \{100, 110\}$이다. 오른쪽 두개 비트에서 다를 수 있는데, 부분집합이어야 하므로 $111$같은건 안된다. 이 정의를 이용하면, 어떤 집합도 서로 겹치지 않는 $S(mask, i)$들의 합집합으로 나타낼 수 있게 된다. 점화식 유도 # 점화식은 다음과 같이 두가지로 정의할 수 있겠다. $mask$의 $i$번째 비트가 $0$인 경우 $mask$의 부분집합이 $i$번째 비트에서 $0$만을 가질 수 있으므로 $S(mask, i) = S(mask, i-1)$ $mask$의 $i$번째 비트가 $1$인 경우 $mask$의 부분집합이 $i$번째 비트에서 $0, 1$ 모두 가질 수 있으므로 $S(mask, i) = S(mask, i-1) \cup S(mask \oplus 2^i, i-1)$ 따라서 이를 코드로 나타내면 다음과 같다. for(int mask = 0; mask < (1<<N); mask++) DP[mask] = A[mask]; for(int i = 0; i<N; i++){ for(int mask = 0; mask < (1<<N); mask++){ if(mask & (1<<i)) DP[mask] += DP[mask ^ (1<<i)]; } } 계산 결과 DP에 들어있는 값은 해당 비트마스킹의 부분집합의 합이다. 시간복잡도는 그대로 보이듯이 $O(N2^N)$이다. N차원 누적합 # https://blog.queuedlab.com/posts/sos-dp 를 참고하면, 이를 $N$차원 누적합으로도 해석할 수 있다. 하이퍼 수열과 하이퍼 쿼리 문제에서 $N$차원 누적합 아이디어는 써본적이 있었는데, 이것이 SOS DP와 같다는 것이 신기하다. 앞으로는 포함배제에서 뭔가 줄이고싶으면 한번씩은 의심해보는걸로? imos-hanbyul Trick # 이와 비슷한 내용을 https://qwerasdfzxcl.tistory.com/35 여기서 본적이 있다. 지금 당장은 이해하기 귀찮으므로 이해한 내용은 나중에 추가하겠다. ❔질문 사항 # 🔗 참고 자료 # https://codeforces.com/blog/entry/45223 https://blog.queuedlab.com/posts/sos-dp https://qwerasdfzxcl.tistory.com/35
📝 상세 정리 # 주어진 쿼리포인트와 매우 가까운 데이터 포인트를 찾는 알고리즘
기본적으로는 모든 노드에 대해 확인해봐야하므로 $O(N)$이다. KD-Trees
Locality-Sensitive Hashing (LSH)
Annoy (Approximate Nearest Neighbors Oh Yeah)
Linear Scan Algorithm
이건 선형이자나 머야 ❔질문 사항 # 🔗 참고 자료 # https://dytis.tistory.com/108