FFT 관련 문제들(상대적 쉬움)

* FFT (Fast fourier transform) 문제들

어렵긴 어려운데 "상대적"으로 쉬운 문제들을 소개합니당

1. Golf Bot(https://www.acmicpc.net/problem/10531)

FFT 활용에 가장 기본적인 지수에 대한 처리를 다루는 문제다.

문제는 한 개의 정수 리스트에서 중복을 포함하여 두 수를 뽑아서 더한 결과를 리스트로 만들어야 한다.

들어오는 쿼리가 결과 리스트에 포함되어 있는지 아닌지를로 판단해야 하는 문제임은 쉽게 알 수 있다.

하지만 두 수를 뽑아내서 더하여 리스트를 만드는 것은 의 시간이 걸리므로 명백하게 시간 초과임을 알 수 있다.

여기서 FFT가 등장한다. 곱셈에서 와 를 곱하면 이 된다. 이처럼 와 를 더하기 위해서 지수로 올려놓고 곱셈을 수행하는 것이다.

하나의 수가 최대 200000이므로 MAX_DIST = 200000이다.

차수한계 MAX_DIST인 가능한 거리를 담는 벡터 에 대해

벡터 는 차수한계 2 * MAX_DIST을 가진다. 메모리 공간도 400000이므로 충분하다는 것을 알 수 있다.

FFT를 수행하고 나면 결과 벡터 에 대해 에 해당하는 계수가 0보다 큰지를 보면 가능한지 아닌지를 만에 알 수 있다.

2. Just A Few More Triangles! (피타고라스의 정리, https://www.acmicpc.net/problem/5051)

이 문제를 풀기 위해서는 페르마의 소정리(MODULAR p)에 대해 확실하게 알고 있어야만 한다.

먼저 풀기 전에 직관적인 표를 구성해서 답을 유도해보자.

	1	2	3
	1	1	0

< 표1 - 와  테이블 >

행이 a, 열이 b라고 하자.

	1 + 1	1 + 4	1 + 9
	4 + 1	4 + 4	4 + 9
	9 + 1	9 + 4	9 + 9

< 표2 -  +  테이블 >

	1	2	3
1	2	2	1
2	2	1	1
3	1	1	0

< 표3 -  테이블, 초록색은 를 만족하는 부분이고 빨강색은 이므로 제외한다 >

* 인 에 대해 아래와 같은 수식이 성립한다.

* 표1을 이용하여 경우의 수를 계산해보자.

 테이블에서 나올 수 있는 수의 개수는 이다.

 이 된다.

로 정의하면

로 일반화 시킬 수 있다.

수식에 사용되는 와  모두 개수임을 인지하고 진행하자.

여기서 관찰 포인트는 는 모두 걸렀는데, 모두 포함한다고 가정해보자. 그렇다면 인 집합 A, 인 집합 B, 인 집합 C를 생각해보자.

그러면 A와 B는 대칭적임을 알 수 있기에 아래와 같은 수식이 성립한다.

   결과적으로 수식은 같지만 계산 방식이 달라진다.

   (단, 을 구할 때 는 이어야 한다.)

* 전체 탐색 계산

  1. 표1 구하는 것은 만에 구할 수 있다.

  2. 표2, 3을 구하는 것은 만에 구할 수 있다.

당연히 2.에서 시간초과가 난다.

[ FFT 설계 ]

Modular가 없는 세계를 먼저 생각해보자.

피타고라스 정리에서 차수한계 n에 대해 를 구하기 위해서는 다음 프로시저를 따른다.

  1. 를 담는 차수한계 인 벡터 v를 계산한다. -> 

  2. 를 담는 차수한계 인 벡터 를 FFT로 구한다. -> 

여기서 표1을 구한다음 2.와 매칭하면 답을 구할 수 있다.

이제 Modular가 있는 세계를 생각해보자. 그러면 무엇이 달라지는지 관찰해야 한다.

첫 번째 관찰은 MOD n을 함으로써 가능한 가지수는 없을 때보다 많아진다. n 이상의 것들도 0~n-1 범위로 줄이기 때문이다.

두 번째 관찰은 n 이상의 것을 줄이기 위해서 와  모두 "지수"에 대해 %n을 처리를 해주는 것이다.

이제 0~n-1 지수들로만 가지고 놀면 된다.

위에서 설명한 집합 A, B, C에 대해서  이다. 따라서 에 대해 만으로 을 계산해주고 마지막에 를 해주면 답이 된다. 

+부가 설명)

1. FFT를 구현할 때 결과의 자료형으론 int형으로 충분히 구현이 가능하다. 구조에서 차수 한계 500000이기 때문에 아무리 많아야 500000*2다. 대부분의 FFT 문제에서 int로 충분한 것 같다(물론 FFT를 중간 계산할 때는 double로).

2. 을 구할 때 k는 이어야 한다. 표3을 보면 a, b, c 모두 범위가 1보단 크거나 같고 n보단 작아야하기 때문이다.