Fast Walsh-Hadamard Transform
(convolution/walsh_hadamard_transform.hpp)
Description
Walsh-Hadamard 変換を用いると,bitwise XOR convolution が計算できる.
\[c_k = \sum_{i\oplus j=k} a_i b_j\]
Operations
-
void fwht(vector<T> a)
- 数列 $a$ を高速 Walsh-Hadamard 変換する
- 時間計算量: $O(n\log n)$
-
void ifwht(vector<T> a)
- 数列 $a$ を逆高速 Walsh-Hadamard 変換する
- 時間計算量: $O(n\log n)$
Note
畳み込み |
変換 |
逆変換 |
$\max$ |
zeta 変換 (累積和,下位) |
Möbius 変換 (累積和,下位) |
$\min$ |
zeta 変換 (累積和,上位) |
Möbius 変換 (累積和,上位) |
$\gcd$ |
zeta 変換 (約数,上位) |
Möbius 変換 (約数,上位) |
$\mathrm{lcm}$ |
zeta 変換 (約数,下位) |
Möbius 変換 (約数,下位) |
$\mathrm{bitwise\ and}$ |
zeta 変換 (bit,上位) |
Möbius 変換 (bit,上位) |
$\mathrm{bitwise\ or}$ |
zeta 変換 (bit,下位) |
Möbius 変換 (bit,下位) |
$\mathrm{bitwise\ xor}$ |
Walsh-Hadamard 変換 |
逆 Walsh-Hadamard 変換 |
$+$ |
Fourier 変換,数論変換 |
逆 Fourier 変換,逆数論変換 |
Reference
Required by
Verified with
Code
Back to top page