11618번 - Frightful Formula
Convolution을 계산하는 문제를 FFT로 풀면 실수 오차 때문에 WA가 나는데,
소수로 나눈 나머지를 구할 수 있는 NTT 알고리즘이라는 것이 있다고 들었습니다.
하지만 소수 p가 2^k+1꼴의 소수가 아닌 이상 원시근을 구한 뒤에 어떻게 해야 하는지 잘 모르겠습니다.
NTT에 대해 설명해주시거나 잘 설명되어있는 링크를 주시면 감사하겠습니다. 도와주세요 ㅠ
안녕하세요
https://rkm0959.tistory.com/187 를 참고해보세요
you're welcome in advance.
ㄹㅇㅋㅋ
댓글을 작성하려면 로그인해야 합니다.
ainta 8년 전
Convolution을 계산하는 문제를 FFT로 풀면 실수 오차 때문에 WA가 나는데,
소수로 나눈 나머지를 구할 수 있는 NTT 알고리즘이라는 것이 있다고 들었습니다.
하지만 소수 p가 2^k+1꼴의 소수가 아닌 이상 원시근을 구한 뒤에 어떻게 해야 하는지 잘 모르겠습니다.
NTT에 대해 설명해주시거나 잘 설명되어있는 링크를 주시면 감사하겠습니다. 도와주세요 ㅠ