setfunc/bitwise_transform.hpp

• View this file on GitHub
• Last update: 2026-06-15 22:08:56+09:00
• Include: #include "setfunc/bitwise_transform.hpp"
• Link: View error logs on GitHub Actions

Required by

• graph/chromatic.hpp
• graph/count/count_biconnected_subgraph.hpp
• graph/count/count_bridgeless_subgraph.hpp
• graph/count/count_connected_subgraph.hpp
• graph/count/count_tree_subgraph.hpp
• graph/tutte_polynomial.hpp
• linalg/hafnian.hpp
• setfunc/and_convolution.hpp
• setfunc/hadamard.hpp
• setfunc/or_convolution.hpp
• setfunc/power_projection_of_sps.hpp
• setfunc/ranked_zeta.hpp
• setfunc/sps_composition.hpp
• setfunc/sps_exp.hpp
• setfunc/sps_inv.hpp
• setfunc/sps_log.hpp
• setfunc/subset_convolution.hpp
• setfunc/xor_convolution.hpp
• setfunc/zeta.hpp

Verified with

• test/2_library_checker/convolution/bitwise_and_convolution.test.cpp
• test/2_library_checker/convolution/bitwise_or_convolution.test.cpp
• test/2_library_checker/convolution/bitwise_xor_convolution.test.cpp
• test/2_library_checker/graph/chromatic_number.test.cpp
• test/2_library_checker/graph/chromatic_polynomial.test.cpp
• test/2_library_checker/linear_algebra/hafnian_of_matrix.test.cpp
• test/2_library_checker/set_power_series/composition_sps.test.cpp
• test/2_library_checker/set_power_series/power_projection_of_sps.test.cpp
• test/2_library_checker/set_power_series/powproj_sps.test.cpp
• test/2_library_checker/set_power_series/sps_exp.test.cpp
• test/2_library_checker/set_power_series/subset_convolution.test.cpp
• test/3_yukicoder/1142.test.cpp
• test/3_yukicoder/1753.test.cpp
• test/3_yukicoder/2507.test.cpp

Code

#pragma once

namespace bitwise {

enum class trans_type {
  hadamard,
  superset_zeta,
  superset_mobius,
  subset_zeta,
  subset_mobius,
  ranked_zeta,
  ranked_mobius
};

template <typename ARR>
inline void ranked_add(ARR& a, const ARR& b) {
  for (int d = 0; d < int(a.size()); ++d) a[d] += b[d];
}

template <typename ARR>
inline void ranked_sub(ARR& a, const ARR& b) {
  for (int d = 0; d < int(a.size()); ++d) a[d] -= b[d];
}

template <trans_type type, int N, typename T>
inline void bitwise_transform_fixed(T* a) {
  static_assert(N >= 1 && (N & (N - 1)) == 0);
  if constexpr (N == 1) {
    return;
  } else {
    constexpr int H = N / 2;
    bitwise_transform_fixed<type, H>(a);
    bitwise_transform_fixed<type, H>(a + H);
    if constexpr (type == trans_type::hadamard) {
      for (int i = 0; i < H; ++i) {
        auto x = a[i], y = a[H + i];
        a[i] = x + y, a[H + i] = x - y;
      }
    }
    if constexpr (type == trans_type::superset_zeta) {
      for (int i = 0; i < H; ++i) a[i] += a[H + i];
    }
    if constexpr (type == trans_type::superset_mobius) {
      for (int i = 0; i < H; ++i) a[i] -= a[H + i];
    }
    if constexpr (type == trans_type::subset_zeta) {
      for (int i = 0; i < H; ++i) a[H + i] += a[i];
    }
    if constexpr (type == trans_type::subset_mobius) {
      for (int i = 0; i < H; ++i) a[H + i] -= a[i];
    }
    if constexpr (type == trans_type::ranked_zeta) {
      for (int i = 0; i < H; ++i) ranked_add(a[H + i], a[i]);
    }
    if constexpr (type == trans_type::ranked_mobius) {
      for (int i = 0; i < H; ++i) ranked_sub(a[H + i], a[i]);
    }
  }
}

template <trans_type type, int N, typename T>
inline void bitwise_transform_dispatch(vc<T>& a) {
  if (len(a) == N) {
    return bitwise_transform_fixed<type, N>(a.data());
  }
  if constexpr (N > 1) {
    return bitwise_transform_dispatch<type, N / 2>(a);
  }
}

template <trans_type type, typename T>
inline void bitwise_transform(vc<T>& a) {
  int n = len(a);
  assert(n >= 1);
  assert((n & (n - 1)) == 0);
  assert(n <= (1 << 25));
  bitwise_transform_dispatch<type, 1 << 25>(a);
}
}  // namespace bitwise

#line 2 "setfunc/bitwise_transform.hpp"

namespace bitwise {

enum class trans_type {
  hadamard,
  superset_zeta,
  superset_mobius,
  subset_zeta,
  subset_mobius,
  ranked_zeta,
  ranked_mobius
};

template <typename ARR>
inline void ranked_add(ARR& a, const ARR& b) {
  for (int d = 0; d < int(a.size()); ++d) a[d] += b[d];
}

template <typename ARR>
inline void ranked_sub(ARR& a, const ARR& b) {
  for (int d = 0; d < int(a.size()); ++d) a[d] -= b[d];
}

template <trans_type type, int N, typename T>
inline void bitwise_transform_fixed(T* a) {
  static_assert(N >= 1 && (N & (N - 1)) == 0);
  if constexpr (N == 1) {
    return;
  } else {
    constexpr int H = N / 2;
    bitwise_transform_fixed<type, H>(a);
    bitwise_transform_fixed<type, H>(a + H);
    if constexpr (type == trans_type::hadamard) {
      for (int i = 0; i < H; ++i) {
        auto x = a[i], y = a[H + i];
        a[i] = x + y, a[H + i] = x - y;
      }
    }
    if constexpr (type == trans_type::superset_zeta) {
      for (int i = 0; i < H; ++i) a[i] += a[H + i];
    }
    if constexpr (type == trans_type::superset_mobius) {
      for (int i = 0; i < H; ++i) a[i] -= a[H + i];
    }
    if constexpr (type == trans_type::subset_zeta) {
      for (int i = 0; i < H; ++i) a[H + i] += a[i];
    }
    if constexpr (type == trans_type::subset_mobius) {
      for (int i = 0; i < H; ++i) a[H + i] -= a[i];
    }
    if constexpr (type == trans_type::ranked_zeta) {
      for (int i = 0; i < H; ++i) ranked_add(a[H + i], a[i]);
    }
    if constexpr (type == trans_type::ranked_mobius) {
      for (int i = 0; i < H; ++i) ranked_sub(a[H + i], a[i]);
    }
  }
}

template <trans_type type, int N, typename T>
inline void bitwise_transform_dispatch(vc<T>& a) {
  if (len(a) == N) {
    return bitwise_transform_fixed<type, N>(a.data());
  }
  if constexpr (N > 1) {
    return bitwise_transform_dispatch<type, N / 2>(a);
  }
}

template <trans_type type, typename T>
inline void bitwise_transform(vc<T>& a) {
  int n = len(a);
  assert(n >= 1);
  assert((n & (n - 1)) == 0);
  assert(n <= (1 << 25));
  bitwise_transform_dispatch<type, 1 << 25>(a);
}
}  // namespace bitwise

Back to top page