Fast Walsh-Hadamard Transform
(convolution/walsh_hadamard_transform.hpp)

• View this file on GitHub
• Last update: 2024-01-08 17:31:43+09:00
• Include: #include "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

• Hadamard 変換とbitwise XOR convolution - sapphire15の日記
• Fast Walsh Hadamard Transforms and it’s inner workings - Codeforces

Required by

• Bitwise XOR Convolution (convolution/xor_convolution.hpp)

Verified with

• test/yosupo/bitwise_xor_convolution.test.cpp

Code

#pragma once
#include <bit>
#include <cassert>
#include <vector>

template <typename T>
void fwht(std::vector<T>& a) {
    assert(std::has_single_bit(a.size()));
    const int n = a.size();
    for (int h = 1; h < n; h <<= 1) {
        for (int i = 0; i < n; i += h << 1) {
            for (int j = i; j < i + h; ++j) {
                T x = a[j], y = a[j | h];
                a[j] = x + y;
                a[j | h] = x - y;
            }
        }
    }
}

template <typename T>
void ifwht(std::vector<T>& a) {
    assert(std::has_single_bit(a.size()));
    const int n = a.size();
    const T inv2 = T(1) / 2;
    for (int h = 1; h < n; h <<= 1) {
        for (int i = 0; i < n; i += h << 1) {
            for (int j = i; j < i + h; ++j) {
                T x = a[j], y = a[j | h];
                a[j] = (x + y) * inv2;
                a[j | h] = (x - y) * inv2;
            }
        }
    }
}

#line 2 "convolution/walsh_hadamard_transform.hpp"
#include <bit>
#include <cassert>
#include <vector>

template <typename T>
void fwht(std::vector<T>& a) {
    assert(std::has_single_bit(a.size()));
    const int n = a.size();
    for (int h = 1; h < n; h <<= 1) {
        for (int i = 0; i < n; i += h << 1) {
            for (int j = i; j < i + h; ++j) {
                T x = a[j], y = a[j | h];
                a[j] = x + y;
                a[j | h] = x - y;
            }
        }
    }
}

template <typename T>
void ifwht(std::vector<T>& a) {
    assert(std::has_single_bit(a.size()));
    const int n = a.size();
    const T inv2 = T(1) / 2;
    for (int h = 1; h < n; h <<= 1) {
        for (int i = 0; i < n; i += h << 1) {
            for (int j = i; j < i + h; ++j) {
                T x = a[j], y = a[j | h];
                a[j] = (x + y) * inv2;
                a[j | h] = (x - y) * inv2;
            }
        }
    }
}

Back to top page