Polynomial Convolution
(lib/math/convolution.hpp)

• View this file on GitHub
• Last update: 2024-06-14 09:23:51+08:00
• Include: #include "lib/math/convolution.hpp"

Depends on

• Internal Definition (lib/internal.hpp)

Verified with

• verify/math/bitwise_and_convolution.test.cpp
• verify/math/bitwise_xor_convolution.test.cpp
• verify/math/convolution.test.cpp
• verify/math/subset_convolution.test.cpp

Code

/**
 * @brief Polynomial Convolution
 */
#pragma once
#include "lib/internal.hpp"

namespace poly {

namespace details {

vec<u32> r[30];
const vec<u32> &calc(const u32 n)
{
  if (r[n].size()) return r[n];
  u32 q = 1 << n, p = q / 2;
  r[n].resize(q);
  for (u32 i = 1; i < q; i++) {
    r[n][i] = r[n][i / 2] / 2;
    if (i % 2) r[n][i] += p;
  }
  return r[n];
}

} // namespace details

template <typename T> void reverse_transform(const u32 n, vec<T> &a)
{
  const auto &r = details::calc(n);
  u32 q = 1 << n;
  for (u32 i = 0; i < q; i++) {
    if (i < r[i]) std::swap(a[i], a[r[i]]);
  }
}

template <bool d, class B, class I, typename T>
void fourier_transform(const u32 n, vec<T> &a, B base, I inv, T e)
{
  reverse_transform(n, a);
  u32 q = 1 << n;
  for (u32 h = 2; h <= q; h *= 2) {
    T b = base(h);
    for (u32 j = 0; j < q; j += h) {
      T w(e);
      for (u32 k = j, l = h / 2; k < j + l; k++) {
        T u = a[k], v = w * a[k + l];
        a[k] = u + v;
        a[k + l] = u - v;
        w = w * b;
      }
    }
  }
  if constexpr (d) {
    for (u32 i = 0; i < q; i++) inv(a[i], q);
  }
}

} // namespace poly

namespace poly {

namespace bit {

template <typename T> void compliment(u32 n, vec<T> &a)
{
  u32 q = 1 << n;
  for (u32 i = 0; i < q; i++) {
    if (i & 1) std::swap(a[i], a[(~i) & (q - 1)]);
  }
}

template <bool dir, typename T> void sosdp(u32 n, vec<T> &a)
{
  u32 q = 1 << n;
  for (u32 i = 0; i < n; i++) {
    for (u32 j = 0; j < q; j++) {
      if ((j >> i) & 1) {
        if constexpr (!dir) a[j] += a[j ^ (1 << i)];
        else a[j] -= a[j ^ (1 << i)];
      }
    }
  }
}

} // namespace bit

} // namespace poly

Traceback (most recent call last):
  File "/home/runner/.local/lib/python3.10/site-packages/onlinejudge_verify/documentation/build.py", line 71, in _render_source_code_stat
    bundled_code = language.bundle(stat.path, basedir=basedir, options={'include_paths': [basedir]}).decode()
  File "/home/runner/.local/lib/python3.10/site-packages/onlinejudge_verify/languages/cplusplus.py", line 187, in bundle
    bundler.update(path)
  File "/home/runner/.local/lib/python3.10/site-packages/onlinejudge_verify/languages/cplusplus_bundle.py", line 312, in update
    raise BundleErrorAt(path, i + 1, "#pragma once found in a non-first line")
onlinejudge_verify.languages.cplusplus_bundle.BundleErrorAt: lib/math/convolution.hpp: line 4: #pragma once found in a non-first line

Back to top page