集合冪級数 (set power series) の指数
(include/emthrm/math/convolution/exp_of_set_power_series.hpp)

• View this file on GitHub
• Last update: 2023-08-15 15:09:21+09:00
• Include: #include "emthrm/math/convolution/exp_of_set_power_series.hpp"

集合冪級数 $(\lbrace f \in 2^{\lbrack n \rbrack} \to K \rbrace, +, \ast)$ を考える。$f(\emptyset) = 0$ を満たす $f \in 2^{\lbrack n \rbrack} \to K$ に対して

\[\exp{f} \mathrel{:=} \sum_{k = 0}^\infty \frac{f^k}{k!}\]

で定義される $\exp$ である。

時間計算量

$O(2^N N^2)$

仕様

名前	戻り値	要件
template <int MaxN, typename T> std::vector<T> exp_of_set_power_series(const std::vector<T>& f);	$\exp{f}$	$n \leq \mathrm{MaxN}$ $f(\emptyset) = 0$

参考文献

• https://suisen-kyopro.hatenablog.com/entry/2023/04/07/041318
• https://nyaannyaan.github.io/library/set-function/exp-of-set-power-series.hpp

TODO

• 集合冪級数
  • https://maspypy.com/category/%e9%9b%86%e5%90%88%e3%81%b9%e3%81%8d%e7%b4%9a%e6%95%b0
  • 多項式との合成
    • https://maspypy.com/%e9%9b%86%e5%90%88%e3%81%b9%e3%81%8d%e7%b4%9a%e6%95%b0%e9%96%a2%e9%80%a3-2-%e5%a4%9a%e9%a0%85%e5%bc%8f%e3%81%a8%e3%81%ae%e5%90%88%e6%88%90
    • https://suisen-kyopro.hatenablog.com/entry/2023/04/07/041318
    • https://nyaannyaan.github.io/library/set-function/polynomial-composite-set-power-series.hpp
    • https://judge.yosupo.jp/problem/polynomial_composite_set_power_series
    • 問題例 “We Love Forest”
      • https://atcoder.jp/contests/abc253/editorial/4028
  • 対数
    • 問題例 “Lights Out on Connected Graph”
      • https://twitter.com/noshi91/status/1315347967990140928
      • https://twitter.com/noshi91/status/1315504267927584768
      • https://twitter.com/noshi91/status/1339077655715430401
      • https://maspypy.com/%e9%9b%86%e5%90%88%e3%81%b9%e3%81%8d%e7%b4%9a%e6%95%b0%e9%96%a2%e9%80%a3-4-%e5%95%8f%e9%a1%8c%e4%be%8b#toc3
      • https://nyaannyaan.github.io/library/set-function/subset-convolution.hpp.html
    • 問題例 “Connectivity 2”
      • https://maspypy.com/%e9%9b%86%e5%90%88%e3%81%b9%e3%81%8d%e7%b4%9a%e6%95%b0%e9%96%a2%e9%80%a3-4-%e5%95%8f%e9%a1%8c%e4%be%8b#toc2
      • https://atcoder.jp/contests/abc213/submissions/24925408
    • 問題例 “Electric Circuit”
      • https://atcoder.jp/contests/abc321/tasks/abc321_g
  • 累乗
    • https://twitter.com/_su1sen/status/1425871066916790281
    • 問題例 “K-Coloring”
      • https://maspypy.com/%e9%9b%86%e5%90%88%e3%81%b9%e3%81%8d%e7%b4%9a%e6%95%b0%e9%96%a2%e9%80%a3-4-%e5%95%8f%e9%a1%8c%e4%be%8b#toc5
      • https://twitter.com/noshi91/status/1637451650402234373
  • 平方根
    • 問題例 “Hierarchical Phylogeny”
      • https://hos-lyric.hatenablog.com/entry/2021/01/14/201231
      • https://twitter.com/heno_code/status/1342124587849400320
      • https://twitter.com/tpyneriver/status/1356095139035242497
  • 高速化
    • https://37zigen.com/subset-convolution/#i-2
    • https://twitter.com/tpyneriver/status/1425483346927177736

Submissons

https://judge.yosupo.jp/problem/exp_of_set_power_series

Depends on

• subset convolution (include/emthrm/math/convolution/subset_convolution.hpp)

Verified with

• 数学/畳み込み/集合冪級数の指数 (test/math/convolution/exp_of_set_power_series.test.cpp)

Code

#ifndef EMTHRM_MATH_CONVOLUTION_EXP_OF_SET_POWER_SERIES_HPP_
#define EMTHRM_MATH_CONVOLUTION_EXP_OF_SET_POWER_SERIES_HPP_

#include <algorithm>
#include <bit>
#include <cassert>
#include <iterator>
#include <vector>

#include "emthrm/math/convolution/subset_convolution.hpp"

namespace emthrm {

template <int MaxN, typename T>
std::vector<T> exp_of_set_power_series(const std::vector<T>& f) {
  assert(std::has_single_bit(f.size()) && f[0] == 0);
  const int n = std::countr_zero(f.size());
  assert(n <= MaxN);
  std::vector<T> exponential{1};
  exponential.reserve(1 << n);
  for (int i = 0; i < n; ++i) {
    std::ranges::copy(subset_convolution<MaxN>(
                          exponential,
                          std::vector(std::next(f.begin(), 1 << i),
                                      std::next(f.begin(), 1 << (i + 1)))),
                      std::back_inserter(exponential));
  }
  return exponential;
}

}  // namespace emthrm

#endif  // EMTHRM_MATH_CONVOLUTION_EXP_OF_SET_POWER_SERIES_HPP_

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



#include <algorithm>
#include <bit>
#include <cassert>
#include <iterator>
#include <vector>

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



#include <array>
#line 7 "include/emthrm/math/convolution/subset_convolution.hpp"
#include <utility>
#line 9 "include/emthrm/math/convolution/subset_convolution.hpp"

namespace emthrm {

template <int MaxN, typename T>
std::vector<T> subset_convolution(
    const std::vector<T>& f, const std::vector<T>& g) {
  using Polynomial = std::array<T, MaxN + 1>;
  assert(std::has_single_bit(f.size()) && f.size() == g.size());
  const int n = std::countr_zero(f.size());
  assert(n <= MaxN);
  const int domain_size = 1 << n;
  const auto ranked_zeta_transform =
      [n, domain_size](const std::vector<T>& f) -> std::vector<Polynomial> {
    std::vector a(domain_size, Polynomial{});
    for (int i = 0; i < domain_size; ++i) {
      a[i][std::popcount(static_cast<unsigned int>(i))] = f[i];
    }
    for (int bit = 1; bit < domain_size; bit <<= 1) {
      for (int i = 0; i < domain_size; ++i) {
        if ((i & bit) == 0) {
          for (int degree = 0; degree <= n; ++degree) {
            a[i | bit][degree] += a[i][degree];
          }
        }
      }
    }
    return a;
  };
  std::vector<Polynomial> a = ranked_zeta_transform(f);
  const std::vector<Polynomial> b = ranked_zeta_transform(g);
  for (int i = 0; i < domain_size; ++i) {
    // Hadamard product
    for (int degree_of_a = n; degree_of_a >= 0; --degree_of_a) {
      const T tmp = std::exchange(a[i][degree_of_a], T{});
      for (int degree_of_b = 0; degree_of_a + degree_of_b <= n; ++degree_of_b) {
        a[i][degree_of_a + degree_of_b] += tmp * b[i][degree_of_b];
      }
    }
  }
  for (int bit = 1; bit < domain_size; bit <<= 1) {
    for (int i = 0; i < domain_size; ++i) {
      if ((i & bit) == 0) {
        for (int degree = 0; degree <= n; ++degree) {
          a[i | bit][degree] -= a[i][degree];
        }
      }
    }
  }
  std::vector<T> c(domain_size);
  for (int i = 0; i < domain_size; ++i) {
    c[i] = a[i][std::popcount(static_cast<unsigned int>(i))];
  }
  return c;
}

}  // namespace emthrm


#line 11 "include/emthrm/math/convolution/exp_of_set_power_series.hpp"

namespace emthrm {

template <int MaxN, typename T>
std::vector<T> exp_of_set_power_series(const std::vector<T>& f) {
  assert(std::has_single_bit(f.size()) && f[0] == 0);
  const int n = std::countr_zero(f.size());
  assert(n <= MaxN);
  std::vector<T> exponential{1};
  exponential.reserve(1 << n);
  for (int i = 0; i < n; ++i) {
    std::ranges::copy(subset_convolution<MaxN>(
                          exponential,
                          std::vector(std::next(f.begin(), 1 << i),
                                      std::next(f.begin(), 1 << (i + 1)))),
                      std::back_inserter(exponential));
  }
  return exponential;
}

}  // namespace emthrm

Back to top page