글 읽기 - 시간 제한을 줄여 주세요.

https://solved.ac/contribute/1... 에 따르면 단순 곱셈이 통과된다고 합니다. 배열의 한 칸마다 7자리를 저장하고 크기 42858의 배열 두 개를 O(N^2)에 곱하는 방식입니다.

800 ms 정도로 주면 막을 수 있을 것 같은데, 문제는 FFT 풀이 중에도 800 ms를 넘는 게 조금 있다는 것입니다. 재귀로 FFT를 구현하면 얼마나 걸리는지는 테스트해 보지 않았습니다.

망했어요

+ 제 재귀 구현은 1자리씩 저장했을 때 1512ms, 2자리씩 저장했을 때 768ms가 나옵니다

큰 수 곱셈 (3)이 필요해진 것 같군요

제한은 몇이 적당할지 테스트해보고 (3)으로 새로 만들고 이 문제 번외처리하겠습니다.

FFT 구현을 보통 2^n 단위로 동작하게 하니까 두 수의 최대 길이를 524288로 올리면 어떤가요?

제한을 올릴 수는 없습니다.

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

Baekjoon Online Judge