数学/畳み込み/高速ゼータ変換
(test/math/convolution/fast_zeta_transform.test.cpp)

• View this file on GitHub
• Last update: 2023-07-21 12:14:05+09:00
• Problem: https://atcoder.jp/contests/arc100/tasks/arc100_c

Depends on

• 高速ゼータ変換 (fast zeta transform) (include/emthrm/math/convolution/fast_zeta_transform.hpp)

Code

/*
 * @title 数学/畳み込み/高速ゼータ変換
 *
 * verification-helper: IGNORE
 * verification-helper: PROBLEM https://atcoder.jp/contests/arc100/tasks/arc100_c
 */

#include <algorithm>
#include <array>
#include <functional>
#include <iostream>
#include <utility>
#include <vector>

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

int main() {
  int n;
  std::cin >> n;
  std::vector<std::pair<int, int>> a(1 << n, {0, 0});
  for (int i = 0; i < (1 << n); ++i) {
    std::cin >> a[i].first;
  }
  a = emthrm::fast_zeta_transform<false>(
          a, std::make_pair(0, 0),
          [](const std::pair<int, int>& a, const std::pair<int, int>& b)
              -> std::pair<int, int> {
            std::array<int, 4> tmp{a.first, a.second, b.first, b.second};
            std::sort(tmp.begin(), tmp.end(), std::greater<int>());
            return {tmp[0], tmp[1]};
          });
  std::vector<int> ans(1 << n);
  for (int i = 0; i < (1 << n); ++i) {
    ans[i] = a[i].first + a[i].second;
  }
  for (int i = 1; i < (1 << n); ++i) {
    ans[i] = std::max(ans[i], ans[i - 1]);
    std::cout << ans[i] << '\n';
  }
  return 0;
}

#line 1 "test/math/convolution/fast_zeta_transform.test.cpp"
/*
 * @title 数学/畳み込み/高速ゼータ変換
 *
 * verification-helper: IGNORE
 * verification-helper: PROBLEM https://atcoder.jp/contests/arc100/tasks/arc100_c
 */

#include <algorithm>
#include <array>
#include <functional>
#include <iostream>
#include <utility>
#include <vector>

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



#include <bit>
#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 16 "test/math/convolution/fast_zeta_transform.test.cpp"

int main() {
  int n;
  std::cin >> n;
  std::vector<std::pair<int, int>> a(1 << n, {0, 0});
  for (int i = 0; i < (1 << n); ++i) {
    std::cin >> a[i].first;
  }
  a = emthrm::fast_zeta_transform<false>(
          a, std::make_pair(0, 0),
          [](const std::pair<int, int>& a, const std::pair<int, int>& b)
              -> std::pair<int, int> {
            std::array<int, 4> tmp{a.first, a.second, b.first, b.second};
            std::sort(tmp.begin(), tmp.end(), std::greater<int>());
            return {tmp[0], tmp[1]};
          });
  std::vector<int> ans(1 << n);
  for (int i = 0; i < (1 << n); ++i) {
    ans[i] = a[i].first + a[i].second;
  }
  for (int i = 1; i < (1 << n); ++i) {
    ans[i] = std::max(ans[i], ans[i - 1]);
    std::cout << ans[i] << '\n';
  }
  return 0;
}

Back to top page