ps:fwht
Fast Walsh Hadamard Transform (FWHT)
- 참고
- https://gina65.tistory.com/30 : FFT를 모르는 상태에서도 이해가 가능한 설명 + 코드가 포함되어있음 + or/and convolution에 대해서도 설명되어있음
- https://cubelover.tistory.com/19 : FWHT에 대한 설명은 짧지만, gina65 와 약간 다르게 구현된 코드가 있음
- 두개의 수열 f(n)과 g(n)에 대한 discrete convolution 은 $ (f*g)(m)=\sum _{n}{f(n)g(m-n)}\ $ 으로 정의된다.
- 이것은 두개의 다항식을 계수들을 수열로 표기했을때, 두개의 다항식을 곱한 결과식의 계수에 해당된다. 또한 두개의 자연수의 집합이 주어졌을때, 두 집합에서 뽑은 원소 페어의 합들로 만든 집합을 구하는데에도 사용될 수 있다.
- FFT를 이용해서 빠르게 계산할 수 있음이 잘 알려져있다.
- XOR convolution은 일반적인 discrete convolution과 비슷하게 정의된다. $ (f*g)(m)=\sum _{n}{f(n)g(m xor n)}\ $.
- 두개의 자연수의 집합이 주어졌을때, 두 집합에서 각각 한개씩 원소를 뽑아서 원소쌍들을 만들었을때, 그 xor값들을 모은 집합을 계산하는 방법이다.
- FWHT라는 FFT와 유사한 아이디어를 사용해서 O(nlogn)에 구할 수 있다. 여기에 대한 설명은 위에 있는 링크들로 대체..
- 실제 구현은 오히려 FFT보다도 간단하다. 복소수를 필요로 하지도 않는다.
구현
관련 문제
- 14878 : 약간의 응용이 들어가긴 하지만, 가장 기본적인 문제이다
- 13758 : 사실상 거듭제곱의 빠른 계산 (Exponentiation by squaring)은 이 레벨에서는 당연히 알고 있는 거라고 생각하면, 이 문제가 더 응용면에서 단순할 수도 있다.
- 14555 : 이것도 응용 난이도는 어렵지 않지만, 스프라그-그런디 정리를 알고 있어야 한다.
ps/fwht.txt · 마지막으로 수정됨: 2023/09/10 10:31 저자 teferi
토론