고속 아다마르 변환(XOR 합성곱) 계산기

c[i] = Σ_{j⊕k=i} a[j]·b[k]로, 「인덱스를 XOR 하면 i가 되는 모든 짝의 곱을 더한 것」입니다. 비트마스크 DP나 부분집합을 다루는 문제에서 자주 나옵니다. 곧이곧대로 하면 O(n²)이지만 아다마르 변환을 쓰면 O(n log n)입니다.

FFT는 인덱스가 「더해지는」 합성곱을, 아다마르 변환은 인덱스가 「XOR 되는」 합성곱을 풉니다. 전혀 다른 연산이라 서로 대신할 수 없습니다. 뼈대는 같지만 회전인자가 FFT는 복소수, 아다마르는 ±1뿐입니다.

회전인자가 ±1뿐이라 곱셈 자체가 없고 더하기와 빼기만 하기 때문입니다. FFT는 복소수 회전인자를 쓰므로 정수 입력에도 부동소수점 오차가 끼어 답을 반올림해야 하고, 값이 커지면 그 반올림이 틀리기도 합니다. 아다마르 변환은 정수 입력이면 정수 답이 그대로 나옵니다.

순변환을 한 번 더 하고 n으로 나누면 됩니다. H² = n·I이기 때문입니다. 역변환 코드를 따로 쓸 필요가 없어 구현이 몇 줄로 끝납니다.

됩니다. OR은 부분집합 합(제타 변환)을, AND는 상위집합 합을 씌운 뒤 점곱하고 되돌립니다. 뫼비우스 변환은 제타의 덧셈을 뺄셈으로 바꾼 것뿐입니다. 셋 다 O(n log n)이고 정수 연산만 씁니다.

0으로 채웁니다. 인덱스를 비트로 다루기 때문에 2의 거듭제곱이어야 합니다. 0을 채워도 답이 달라지지 않는 것은 곱이 0이 되어 어디에도 보태지 않기 때문입니다.

비트마스크 DP에서 부분집합을 합칠 때, 선형대수에서 XOR 기저를 다룰 때, 그리고 부호이론(월시 함수)과 CDMA 확산 코드에도 쓰입니다. 경쟁 프로그래밍에서는 「XOR이 k인 짝의 개수」류 문제의 표준 도구입니다.

전송되지 않습니다. 계산은 모두 브라우저 안에서 이루어지고 넣은 값은 이 기기에만 남습니다.