高速ウォルシュ-アダマール変換/逆変換 (Fast Walsh Hadamard Transform / Inverse Transform)
(src/math/convolution/fast-walsh-hadamard-transform.hpp)

• View this file on GitHub
• Last update: 2023-07-30 00:54:52+09:00
• Include: #include "src/math/convolution/fast-walsh-hadamard-transform.hpp"

高速ウォルシュ-アダマール変換 / 逆変換

Depends on

• rep 構造体 (src/cpp-template/header/rep.hpp)
• size alias (src/cpp-template/header/size-alias.hpp)

Required by

• src/math/convolution/bitwise-and-convolution.hpp
• src/math/convolution/bitwise-xor-convolution.hpp

Verified with

• test/atcoder/abc212_h.test.cpp
• test/library-checker/bitwise_and_convolution.test.cpp
• test/library-checker/bitwise_xor_convolution.test.cpp

Code

#pragma once

#include "src/cpp-template/header/rep.hpp"
#include "src/cpp-template/header/size-alias.hpp"

#include <cassert>
#include <vector>

namespace luz {

  template < typename T, typename F >
  void fast_walsh_hadamard_transform(std::vector< T > &f, F op) {
    const usize n = f.size();
    assert((n & (n - 1)) == 0);
    usize i = 1;
    while (i < n) {
      usize j = 0;
      while (j < n) {
        for (usize k: rep(0, i)) {
          op(f[j + k], f[j + k + i]);
        }
        j += i << 1;
      }
      i <<= 1;
    }
  }

} // namespace luz

#line 2 "src/math/convolution/fast-walsh-hadamard-transform.hpp"

#line 2 "src/cpp-template/header/rep.hpp"

#line 2 "src/cpp-template/header/size-alias.hpp"

#include <cstddef>

namespace luz {

  using isize = std::ptrdiff_t;
  using usize = std::size_t;

} // namespace luz
#line 4 "src/cpp-template/header/rep.hpp"

#include <algorithm>

namespace luz {

  struct rep {
    struct itr {
      usize i;
      constexpr itr(const usize i) noexcept: i(i) {}
      void operator++() noexcept {
        ++i;
      }
      constexpr usize operator*() const noexcept {
        return i;
      }
      constexpr bool operator!=(const itr x) const noexcept {
        return i != x.i;
      }
    };
    const itr f, l;
    constexpr rep(const usize f, const usize l) noexcept
        : f(std::min(f, l)),
          l(l) {}
    constexpr auto begin() const noexcept {
      return f;
    }
    constexpr auto end() const noexcept {
      return l;
    }
  };

  struct rrep {
    struct itr {
      usize i;
      constexpr itr(const usize i) noexcept: i(i) {}
      void operator++() noexcept {
        --i;
      }
      constexpr usize operator*() const noexcept {
        return i;
      }
      constexpr bool operator!=(const itr x) const noexcept {
        return i != x.i;
      }
    };
    const itr f, l;
    constexpr rrep(const usize f, const usize l) noexcept
        : f(l - 1),
          l(std::min(f, l) - 1) {}
    constexpr auto begin() const noexcept {
      return f;
    }
    constexpr auto end() const noexcept {
      return l;
    }
  };

} // namespace luz
#line 5 "src/math/convolution/fast-walsh-hadamard-transform.hpp"

#include <cassert>
#include <vector>

namespace luz {

  template < typename T, typename F >
  void fast_walsh_hadamard_transform(std::vector< T > &f, F op) {
    const usize n = f.size();
    assert((n & (n - 1)) == 0);
    usize i = 1;
    while (i < n) {
      usize j = 0;
      while (j < n) {
        for (usize k: rep(0, i)) {
          op(f[j + k], f[j + k + i]);
        }
        j += i << 1;
      }
      i <<= 1;
    }
  }

} // namespace luz

Back to top page