글 읽기 - 르모앙의 추측 fft 구현 방식에 따른 시간 초과

minsiwon00 2년 전 2

르모앙의 추측을 fft 를 사용해서 풀었습니다.

그런데 구현 방식에 따라 시간초과와 맞았습니다 가 갈렸습니다.

저는 13279/곱의 합 쿼리 를 풀 때도 이 문제에서 시간초과가 난 첫 번째 방식을 사용했었고,

아무리 코드를 들여다 봐도 두 개의 결정적인 차이를 모르겠어서

왜 첫번째 방식으로 구현했을 때 시간초과가 나는지 질문 글 남깁니다.

두 방식이 시간초과와 맞았습니다를 가를 정도로 차이가 큰 것인지, 그렇다면 이유는 무엇인지 고수님들의 답변 기다립니다.

감사합니다.

//첫 번째 방식(시간초과)
//출처: https://www.acmicpc.net/board/view/71612
void fft(cv &a,int is_inv){
	
	int n = a.size();
	for(int i=1,j=0;i<n;i++){
		int t = n>>1;
		while(!((j^=t)&t)) t>>=1;
		if(i<j) swap(a[i],a[j]);
	}
	for(int i=1;i<n;i<<=1){
		double x =  (pi/i)*(2*is_inv-1);
		for(int j=0;j<n;j+=i<<1){
			for(int k=0;k<i;k++){
				cpx even = a[j+k];
				cpx odd = cpx(cos(x*k),sin(x*k))*a[i+j+k];
			
				a[i+j+k] = even-odd; //f(-w) = fe(w^2) - z fo(w^2), -w = w+n/2
				a[j+k] = even + odd; //f(w) = fe(w^2) + z fo(w^2)
			}
		}
	}
	if(is_inv){
		for(int i=0;i<n;i++) a[i]/=n;
	}
}

//두 번째 방식(맞았습니다)
//출처:https://kau-algorithm.tistory.com/15
void fft(cv &a,int is_inv){
	
	int n = a.size();
	for(int i=1,j=0;i<n;i++){
		int t = n/2;
		while(!((j^=t)&t)) t/=2;
		if(i<j) swap(a[i],a[j]);
	}
	for(int i=1;i<n;i*=2){
		double x =  (pi/i)*(2*is_inv-1);
		cpx w = cpx(cos(x),sin(x));
		for(int j=0;j<n;j+=i*2){
			cpx z = cpx(1,0);
			for(int k=0;k<i;k++){
				cpx even = a[j+k];
				cpx odd = z*a[i+j+k];
			
				a[i+j+k] = even-odd; //f(-w) = fe(w^2) - z fo(w^2), -w = w+n/2
				a[j+k] = even + odd; //f(w) = fe(w^2) + z fo(w^2)
				z*=w;
			}
		}
	}
	if(is_inv){
		for(int i=0;i<n;i++) a[i]/=n;
	}
}

zenith82114 2년 전 0

시간이 좀 지나긴 했습니다만 답변드립니다.

저도 처음에 시간 초과 맞았다가 cout.tie(NULL); 해주고 패스했습니다.

올려주신 부분에서의 성능 차는 없다시피 할 것 같습니다.

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

문제

문제

출처

ICPC

르모앙의 추측 fft 구현 방식에 따른 시간 초과

minsiwon00 2년 전 2

zenith82114 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말