글 읽기 - 뭔가를 놓친거같은데 짚이는게 없어요

tennma 4년 전 0

벡터 둘을 받아서 FFT로 합성곱 구하는 코드를 짰는데, 예제는 맞게 출력하고 채점에서는 '틀렸습니다' 가 떠요.

XOR의 항등원이 0이니까 합성곱을 담을 벡터의 크기가 합성곱보다 큰건 문제가 안 될 것 같고, (뒤에 남는 0을 XOR해도 값이 같으니까)

제일 작은 입력이 1차항이니까 거기서 반례가 나올거같지도 않은데 뭘 놓쳤는지 짚이는게 없네요.

FFT 코드는 요기서 가져왔어요

https://m.blog.naver.com/PostView.nhn?blogId=kks227&logNo=221633584963&proxyReferer=https%3A%2F%2Fwww.google.com%2F

#include<iostream>
#include<vector>
#include<math.h>
#include<complex>
#include<string>
#include<algorithm>

using namespace std;
typedef complex<double> cpx;
const double PI = acos(-1);

/*FFT, 합성곱 소스코드 출처
https://m.blog.naver.com/PostView.nhn?blogId=kks227&logNo=221633584963&proxyReferer=https%3A%2F%2Fwww.google.com%2F
*/


//FFT
void FFT(vector<cpx> &f, cpx w){
	int n=f.size();
	if(n==1) return;
	
	vector<cpx> even(n/2), odd(n/2);
	for(int i=0; i<n; ++i) (i%2? odd : even)[i/2] = f[i];
	
	FFT(even,w*w);
	FFT(odd,w*w);
	
	cpx wp(1,0);
	for(int i=0; i<n/2; ++i){
		f[i] = even[i] + wp*odd[i];
		f[i+n/2] = even[i] - wp*odd[i];
	  wp *= w;
	}
}

//합성곱:벡터 a,b를 받아서 크기가 (a,b의 크기보다 큰 2의 제곱수중 가장 작은 것*2)인 합성곱을 반환함
vector<int> poly_multiply(vector<int> A, vector<int> B){
	
	vector<cpx> a(A.begin(),A.end());		//convert int vector to complex vector 
	vector<cpx> b(B.begin(),B.end());		
	 
	int n=1;
	int aSize = a.size();
	int bSize = b.size();
	while(n<aSize || n<bSize) n *= 2;
	n *= 2;
	
	vector<cpx> c(n); a.resize(n); b.resize(n); 
	
	cpx w = cpx(cos((2*PI)/n),sin((2*PI/n)));
	FFT(a,w); FFT(b,w);
	
	for(int i = 0; i<n; ++i){
		c[i] = a[i]*b[i];
	} 
	
	FFT(c,cpx(1,0)/w);   //IFFT
	for(int i = 0; i<n; ++i){
		c[i] /= n;
	}
	
	vector<int> ret(n);
	for (int i = 0; i < n; i++){
        ret[i] = (int)round(c[i].real());
    }
	return ret;										//cpx로 연산하고 int로 바꿔서 int로 뱉음 
}

int main(){

	int a,b =0;
	cin>>a>>b;                                    //a,b 의 크기 입력
	
	vector<int> f(a+1), g(b+1);                   //f(x),g(x) 선언
	for(int i=0; i<a+1; ++i) cin>>f[i];
	for(int i=0; i<b+1; ++i) cin>>g[i];           //f(x),g(x) 입력
	
	vector<int> h = poly_multiply(f,g);           //h(x) = f(x)*g(x) 
		
	int ret = 0;                                  //출력값, XOR의 항등원 0으로 초기화
	for(auto elem : h) ret ^= elem;               //원소들을 XOR해줌
	
	cout<<ret;                                    //출력값 출력
	
	
	return 0;	
}

harinboy 4년 전 1

이걸 놓치신 것 같습니다.

1 1

1000000 1000000
1000000 1000000

sait2000 4년 전 1

일단 위에 분이 말씀하신 대로 h(x)의 계수 크기가 상당히 커집니다. 꽤 커집니다. 최대값을 한번 계산해보세요.

그리고 그 최대값을 계산해보면 double형이 정확히 표현할 수 없는 크기란 것을 알 수 있습니다!! (double형의 정확도는 보통(?)의 경우 2진법으로 53자리 10진법으로 17자리쯤입니다)

그래서 이 문제는 그냥 곱하면 안되고 1) 실수 오차를 정말 잘 처리하는 방법을 쓰거나 2) 아예 정수를 사용하는 FFT의 변형을 사용하거나 해야합니다.

tennma 4년 전 0

최대값을 확인안했었네요 감사합니다

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

문제

문제

출처

ICPC

뭔가를 놓친거같은데 짚이는게 없어요

tennma 4년 전 0

harinboy 4년 전 1

sait2000 4년 전 1

tennma 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말