1000 500 1 2 3 4 (...) 997 998 999 1000 [o] 500 ~ 500000 [x] 0 ~ 524288
13575번 - 보석 가게
1000 500 1 2 3 4 (...) 997 998 999 1000 [o] 500 ~ 500000 [x] 0 ~ 524288
헐 및힌 감사합니다ㅠㅜ
그 부분을 미처 고려하지 못했네요.. 그럼 NTT를 사용해야 하는 걸까요? 아니면 bool 연산만을 수행하는 특수한 고속 푸리에 변환이 존재하는 것으로 알고 있는데, 해당 방법이 더 나은가요? 이런 질문 죄송하지만 혹시 어느 방법의 구현 난이도가 더 괜찮을지(?) 알고 싶습니다…
+) 그냥 result[i] != 0이면 1로 강제 리셋시켜서 해결했습니다
댓글 달아주신 zenith82114, doju님 모두 감사합니다
++) 답글의 소스 코드를 지울 수 없어 부득이하게 중간에 있던 댓글 하나를 삭제했습니다. k보다 작은 값을 출력하는 오류를 수정한 코드였습니다.
c[k] = OR_{i + j = k} (a[i] AND b[j])
위의 형태, 말하자면 "Boolean convolution"을 제곱 미만 시간에 general하게 풀 수 있는 알고리즘은 아쉽게도 아직 등장하지 않았습니다. {+, *}가 Z 혹은 Z/pZ에서 ring을 이루는 데 반해 {OR, AND}는 {0, 1}에서 additive하지 않은 (1 OR 1 = 1) semiring을 이루기 때문에 Fourier transform 계열의 알고리즘들을 바로 접목하기 어렵습니다. OR가 아닌 XOR였다면 Z2에서의 ring이 되어 FFT/NTT가 가능합니다.
AND Convolution이나 OR Convolution을 들어보셨다면, 이것들은
c[k] = sum_{i AND(OR) j = k} (a[i] * b[j])
의 형태를 지칭, 위에서 말한 것과는 다른 세팅입니다(AND, OR가 들어간 위치가 다르죠).
질문자 분께서 하신 것처럼 exp-by-sqr를 하되 매 step마다 nonzero들을 1로 눌러주는 방식이 정해가 아닐까 생각합니다.
친절한 설명 다시 한 번 감사드립니다:)
댓글을 작성하려면 로그인해야 합니다.
luckyandykang 1년 전
분할 정복을 이용한 거듭제곱을 다항식에 대해 수행해주고 카운팅을 했습니다.
혹시 몰라 계수를 비롯한 모든 요소에 int 대신 long long 자료형을 사용해도 틀렸습니다만 받게 되네요.
오버플로 관련인지 로직의 오류인지도 모르겠고 특히 로직이라면 왜 틀렸는지 도저히 알기 어렵습니다.
예제 입출력은 모두 맞고, 1%에서 틀립니다.
고수분들의 조언 부탁드리겠습니다.