글 읽기 - 문제의 해법 중 하나인 FFT에 관련하여 질문이 있습니다 (스포주의)

h0ngjun7 5년 전 2

P(x) : 입력으로 들어온 수열에서, 앞에서부터 누적 xor 연산하여 값이 x인 것의 개수

라고 정의할 때에

D(x^y) = Sigma( P(x) * P(y) ) 를 계산해서 문제를 풀 수 있었습니다.

저는 처음에 D배열을 카라츠바 알고리즘으로 먼저 해결한 뒤에, fft로 푸신 분들의 코드를 보면서 fft로 다시 풀어보았는데요.

아래 부분 "코드1"이 일반적인 DFT 코드라고 알고 있습니다.

invert가 0일 때에는 coefficient form에서 point value form

invert가 1일 때에는 point value form에서 coefficient form으로 변환해준다고 알고 있습니다.

그 과정에서 복소수가 쓰이구요.

일반적인 곱셈은 D(x+y) = Sigma(P(x) * Q(y))인데 아래 코드에서 복소수 관련 부분만 다 지우니("코드2")

왜 D(x^y)가 구해지는지 잘 모르겠습니다.

도움을 주시면 감사하겠습니다.

//코드1 : 일반적인 곱셈
void dft(vector <base> &a, bool invert) {
	int n = sz(a);
	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 L = 2; L <= n; L <<= 1) {
		long double ang = 2 * M_PI / L*(invert ? -1 : 1);
		base wL(cos(ang), sin(ang));
		for (int i = 0; i < n; i += L) {
			base w(1);
			for (int j = 0; j < L / 2; j++) {
				base u = a[i + j], v = a[i + j + L / 2] * w;
				a[i + j] = u + v;
				a[i + j + L / 2] = u - v;
				w *= wL;
			}
		}
	}
	if (invert) {
		for (int i = 0; i < n; i++) a[i] /= n;
	}
}
//코드2 : 본 문제에서의 곱셈
void dft(VI &a, bool invert) {
	int n = sz(a);
	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 L = 2; L <= n; L <<= 1) {
		for (int i = 0; i < n; i += L) {
			for (int j = 0; j < L / 2; j++) {
				ll u = a[i + j], v = a[i + j + L / 2];
				a[i + j] = u + v;
				a[i + j + L / 2] = u - v;
			}
		}
	}
	if (invert) {
		for (int i = 0; i < n; i++) a[i] /= n;
	}
}

ntopia 5년 전 4

D[k] = sigma( A[i] * B[i^k] ) 꼴로 떨어지는걸 xor convolution 이라고 하는데요

잘 보시면

i^k 는 xor인데, 이걸 비트별로 바라보면

각 비트에서 xor은 Z2 에서의 덧셈이거든요

그래서 Z2 x Z2 x Z2 x ... x Z2 공간에서 이루어지는 multidimensional convolution 이 되고요

이제 multidimensional DFT 를 하면 되는데 그건 그냥 차원별로 평범하게 dft를 하면 돼요

https://en.wikipedia.org/wiki/...

그래서 그 코드를 삭삭 정리하면 코드2 꼴이 나와요.

cubelover 님의 블로그 글에도 설명이 있습니다 : http://cubelover.tistory.com/1...

h0ngjun7 5년 전 0

@ntopia님 감사합니다

카라츠바할 때에 이런 식으로 생각했었거든요

전체 P가 절반을 기준으로 왼쪽부분 X, 오른쪽부분 Y가 있으면 X끼리 곱하고 Y끼리 곱하는 건 차수가 작은 절반 부분에 합이 누적되고

XY 혹은 YX가 차수가 큰 절반 부분에 합이 누적되더라구요.

그 성질과 관련있을까 추측했었는데 비슷한 원리인 것 같아 다행이네요.

h0ngjun7 5년 전 0

위의 댓글에서 절반을 기준으로 나눈 이유가 최상위 비트가 1이냐, 0이냐를 기준으로 나눈 것입니다.

표현이 너무 모호했네요.

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

문제의 해법 중 하나인 FFT에 관련하여 질문이 있습니다 (스포주의)

h0ngjun7 5년 전 2

ntopia 5년 전 4

h0ngjun7 5년 전 0

h0ngjun7 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회 / 고등학교 대회

출처

대학교 대회

도움말