添え字 and での畳み込み
(include/emthrm/math/convolution/and_convolution.hpp)

• View this file on GitHub
• Last update: 2023-02-25 16:35:06+09:00
• Include: #include "emthrm/math/convolution/and_convolution.hpp"

$C_k = \sum_{k = i \circ j} A_i B_j$ を求める。ただし $\circ$ は二項演算である。

添え字 xor での畳み込みには『高速ウォルシュ・アダマール変換 (fast Walsh-Hadamard transform)』を用いる。

時間計算量

$O(N\log{N})$

仕様

添え字 and での畳み込み

名前	戻り値
template <typename T> std::vector<T> and_convolution(std::vector<T> a, std::vector<T> b, const T id = 0);	$A, B$ に対する添え字 and での畳み込み

添え字 or での畳み込み

名前	戻り値
template <typename T> std::vector<T> or_convolution(std::vector<T> a, std::vector<T> b, const T id = 0);	$A, B$ に対する添え字 or での畳み込み

添え字 xor での畳み込み

名前	戻り値
template <typename T> std::vector<T> xor_convolution(std::vector<T> a, std::vector<T> b, const T id = 0);	$A, B$ に対する添え字 xor での畳み込み

添え字 gcd での畳み込み

名前	戻り値
template <typename T> std::vector<T> gcd_convolution(std::vector<T> a, std::vector<T> b);	$A, B$ に対する添え字 gcd での畳み込み

添え字 lcm での畳み込み

名前	戻り値
template <typename T> std::vector<T> lcm_convolution(std::vector<T> a, std::vector<T> b, const int n = -1);	$A, B$ に対する添え字 lcm での畳み込み

参考文献

• https://leaf1415.hatenablog.com/entry/2021/08/04/125751
• https://codeforces.com/blog/entry/48417
• http://kazuma8128.hatenablog.com/entry/2018/05/31/144519
• https://lumakernel.github.io/ecasdqina/algorithm/FastZetaTransform

高速ウォルシュ・アダマール変換

• Bernard J. Fino and V. Ralph Algazi: Unified Matrix Treatment of the Fast Walsh-Hadamard Transform, IEEE Transactions on Computers, Vol. C-25, No. 11, pp. 1142–1146 (1976). https://doi.org/10.1109/TC.1976.1674569
• https://sapphire15.hatenablog.com/entry/2021/09/13/114900
• https://cympfh.cc/aiura/hadamard-xor-convolution
• https://pctprobability.hatenadiary.com/entry/2022/01/10/185418
• https://twitter.com/maspy_stars/status/1350467886775603200

添え字 gcd での畳み込み

• https://noshi91.hatenablog.com/entry/2019/09/23/002445
• https://aprilganmo.hatenablog.com/entry/2020/07/24/190816

添え字 lcm での畳み込み

• https://aprilganmo.hatenablog.com/entry/2020/07/24/190816
• https://yukicoder.me/problems/no/1760

TODO

• https://noshi91.hatenablog.com/entry/2020/10/27/175112
• https://noshi91.hatenablog.com/entry/2023/12/10/163348
• 添え字 gcd での畳み込みを $O(N\log{\log{N}})$ に高速化する。
  • http://noshi91.hatenablog.com/entry/2018/12/27/121649
  • https://github.com/drken1215/algorithm/blob/master/MathAlgebra/fast_gcd_convolution.cpp
• 添え字 xor での畳み込みにおける逆元
  • https://yukicoder.me/problems/no/1753/editorial
• 凸性のある畳み込み
  • https://twitter.com/hotmanww/status/1482185138125832192
  • https://judge.yosupo.jp/problem/min_plus_convolution_convex_convex
  • https://judge.yosupo.jp/problem/min_plus_convolution_convex_arbitrary
• relaxed multiplication
  • https://hly1204.github.io/library/math/formal_power_series/relaxed_convolution.hpp
  • https://qiita.com/Kiri8128/items/1738d5403764a0e26b4c
  • https://hotman78.hatenablog.com/entry/2023/01/04/173507
  • https://maspypy.com/%e5%a4%9a%e9%a0%85%e5%bc%8f%e3%83%bb%e5%bd%a2%e5%bc%8f%e7%9a%84%e3%81%b9%e3%81%8d%e7%b4%9a%e6%95%b0-%e9%ab%98%e9%80%9f%e3%81%ab%e8%a8%88%e7%ae%97%e3%81%a7%e3%81%8d%e3%82%8b%e3%82%82%e3%81%ae#toc38
  • https://twitter.com/noshi91/status/1618178939578634240
  • https://twitter.com/noshi91/status/1692929472507613594
  • https://twitter.com/toomerhs/status/1692939919252164723
  • 問題例 “Bullion”
    • https://atcoder.jp/contests/abc230/editorial/3036
    • https://twitter.com/noshi91/status/1466764432961585166
  • 問題例 “Graph Coloring (hard version)”
    • https://twitter.com/SSRS_cp/status/1617927451958718467
  • 問題例 “Typical Convolution Problem”
    • https://twitter.com/kiri8128/status/1692894996373127280

Submissons

• 添え字 and での畳み込み
• 添え字 or での畳み込み
• 添え字 xor での畳み込み
• 添え字 gcd での畳み込み
• 添え字 lcm での畳み込み

Depends on

• 高速メビウス変換 (fast Mobius transform) (include/emthrm/math/convolution/fast_mobius_transform.hpp)
• 高速ゼータ変換 (fast zeta transform) (include/emthrm/math/convolution/fast_zeta_transform.hpp)

Verified with

• 数学/畳み込み/添え字 and での畳み込み (test/math/convolution/and_convolution.test.cpp)

Code

#ifndef EMTHRM_MATH_CONVOLUTION_AND_CONVOLUTION_HPP_
#define EMTHRM_MATH_CONVOLUTION_AND_CONVOLUTION_HPP_

#include <algorithm>
#include <vector>

#include "emthrm/math/convolution/fast_mobius_transform.hpp"
#include "emthrm/math/convolution/fast_zeta_transform.hpp"

namespace emthrm {

template <typename T>
std::vector<T> and_convolution(std::vector<T> a, std::vector<T> b,
                               const T id = 0) {
  int n = std::max(a.size(), b.size());
  a.resize(n, id);
  b.resize(n, id);
  a = fast_zeta_transform<true>(a, id);
  b = fast_zeta_transform<true>(b, id);
  n = a.size();
  for (int i = 0; i < n; ++i) {
    a[i] *= b[i];
  }
  return fast_mobius_transform<true>(a);
}

}  // namespace emthrm

#endif  // EMTHRM_MATH_CONVOLUTION_AND_CONVOLUTION_HPP_

#line 1 "include/emthrm/math/convolution/and_convolution.hpp"



#include <algorithm>
#include <vector>

#line 1 "include/emthrm/math/convolution/fast_mobius_transform.hpp"



#include <bit>
#line 6 "include/emthrm/math/convolution/fast_mobius_transform.hpp"

namespace emthrm {

template <bool ADDS_SUPERSET, typename T>
std::vector<T> fast_mobius_transform(std::vector<T> a, const T id = 0) {
  const int n = std::bit_ceil(a.size());
  a.resize(n, id);
  for (int i = 1; i < n; i <<= 1) {
    for (int s = 0; s < n; ++s) {
      if (s & i) continue;
      if constexpr (ADDS_SUPERSET) {
        a[s] -= a[s | i];
      } else {
        a[s | i] -= a[s];
      }
    }
  }
  return a;
}

}  // namespace emthrm


#line 1 "include/emthrm/math/convolution/fast_zeta_transform.hpp"



#line 5 "include/emthrm/math/convolution/fast_zeta_transform.hpp"
#include <functional>
#line 7 "include/emthrm/math/convolution/fast_zeta_transform.hpp"

namespace emthrm {

template <bool ADDS_SUPERSET, typename Ring, typename BinOp = std::plus<Ring>>
std::vector<Ring> fast_zeta_transform(
    std::vector<Ring> a, const Ring ID = 0, const BinOp bin_op = BinOp()) {
  const int n = std::bit_ceil(a.size());
  a.resize(n, ID);
  for (int i = 1; i < n; i <<= 1) {
    for (int s = 0; s < n; ++s) {
      if (s & i) continue;
      if constexpr (ADDS_SUPERSET) {
        a[s] = bin_op(a[s], a[s | i]);
      } else {
        a[s | i] = bin_op(a[s | i], a[s]);
      }
    }
  }
  return a;
}

}  // namespace emthrm


#line 9 "include/emthrm/math/convolution/and_convolution.hpp"

namespace emthrm {

template <typename T>
std::vector<T> and_convolution(std::vector<T> a, std::vector<T> b,
                               const T id = 0) {
  int n = std::max(a.size(), b.size());
  a.resize(n, id);
  b.resize(n, id);
  a = fast_zeta_transform<true>(a, id);
  b = fast_zeta_transform<true>(b, id);
  n = a.size();
  for (int i = 0; i < n; ++i) {
    a[i] *= b[i];
  }
  return fast_mobius_transform<true>(a);
}

}  // namespace emthrm

Back to top page