ps:fwht
Fast Walsh Hadamard Transform (FWHT)
- Hadamard는 프랑스 이름이라서 '아다마르' 라고 읽는다 (위키피디아 - 아다마르 행렬)
- 참고
- https://gina65.tistory.com/30 : FFT를 모르는 상태에서도 이해가 가능한 설명 + 코드가 포함되어있음 + or/and convolution에 대해서도 설명되어있음
- https://cubelover.tistory.com/19 : FWHT에 대한 설명은 짧지만, gina65 와 약간 다르게 구현된 코드가 있음
- 가장 단순하게는 xor convolution을 빠르게 계산하는 방법이라고 생각해도 된다.
- XOR convolution은 일반적인 discrete convolution과 비슷하게 정의된다. $ (f*g)(m)=\sum _{n}{f(n)g(m⊕n)}\ $.
- 두개의 자연수의 집합이 주어졌을때, 두 집합에서 각각 한개씩 원소를 뽑아서 원소쌍들을 만들었을때, 그 xor값들을 모은 집합을 계산하는 방법이다.
- FWHT는 FFT와 유사한 아이디어를 사용해서 xor convolution을 O(nlogn)에 구하는 방식이다. 두 수열에 각각 Walsh Hadamard Transform 을 적용한 뒤에 이것들을 pointwise 로 곱하고, 다시 그 결과에 Walsh Hadamard Transform의 역변환을 취하는 과정이다.
- 이제 WHT를 적용한 결과가 어떻게 나오면 pointwise로 곱해서 처리할수 있는지, WHT를 어떻게 빠르게 계산하는지 등은 위에 있는 링크들을 참고하면 된다. 저것만 이해하면 FWHT를 이용해서 xor/or/and convolution을 계산하는 것은 충분히 가능하다
- or과 and에 대한 변환을 빠르게 계산하는 것은 SOS DP라고 불리우는 방법과 동일하다. 저 변환은 zeta transform, mobius transform 이라고도 불리는 것 같다.
- 좀 헷갈릴만한 부분은, 위키피디아의 Fast Walsh–Hadamard transform 항목에서는 xor convolution 같은 얘기는 없고, 뜬금없어 보이는 행렬만 보여주고 있는 것으로 설명방법이 완전히 다르다. 사실 원칙적으로 WHT는 수열에 Hadamard matrix를 곱해주는 방식으로 계산되는 것이고, xor convolution을 위해서는 특정한 형태의 Hadamard matrix가 필요한 것 뿐이다. 근데 어차피 이것을 그냥 곱하지 않고 빠르게 계산하는 방법이 필요한 것이고, xor convolution 과 같은 특정 연산을 설명할 때에는 그냥 바로 결과값으로 변환하는 과정을 설명하는 것으로 충분하기 때문에 굳이 저걸 다 설명하지 않았던 것.
- 관련해서 좀더 자세히는 https://codeforces.com/blog/entry/96003 을 참고
구현
xor convolution
관련 문제
- 14878 : 약간의 응용이 들어가긴 하지만, 가장 기본적인 문제이다
- 13758 : 사실상 거듭제곱의 빠른 계산 (Exponentiation by squaring)은 이 레벨에서는 당연히 알고 있는 거라고 생각하면, 이 문제가 더 응용면에서 단순할 수도 있다.
- 14555 : 이것도 응용 난이도는 어렵지 않지만, 스프라그-그런디 정리를 알고 있어야 한다.
ps/fwht.txt · 마지막으로 수정됨: 2023/11/10 06:36 저자 teferi
토론