comp-library

This documentation is automatically generated by online-judge-tools/verification-helper

View the Project on GitHub luzhiled1333/comp-library

:heavy_check_mark: test/library-checker/bitwise_xor_convolution.test.cpp

Depends on

Code

// verification-helper: PROBLEM https://judge.yosupo.jp/problem/bitwise_xor_convolution

#include "src/math/convolution/bitwise-xor-convolution.hpp"
#include "src/math/modular-arithmetic/static-modint.hpp"

#include <iostream>
#include <vector>

namespace luz {

  void main_() {
    usize n;
    std::cin >> n;

    using mint = modint998244353;
    std::vector< mint > as(1 << n);
    for (mint &a: as) {
      i32 v;
      std::cin >> v;
      a = mint(v);
    }

    std::vector< mint > bs(1 << n);
    for (mint &b: bs) {
      i32 v;
      std::cin >> v;
      b = mint(v);
    }

    auto cs = bitwise_xor_convolution(as, bs);
    for (usize i: rep(0, 1 << n)) {
      std::cout << cs[i].val()
                << (i + 1 == (usize(1) << n) ? "\n" : " ");
    }
  }

} // namespace luz

int main() {
  luz::main_();
}
#line 1 "test/library-checker/bitwise_xor_convolution.test.cpp"
// verification-helper: PROBLEM https://judge.yosupo.jp/problem/bitwise_xor_convolution

#line 2 "src/math/convolution/bitwise-xor-convolution.hpp"

#line 2 "src/cpp-template/header/rep.hpp"

#line 2 "src/cpp-template/header/size-alias.hpp"

#include <cstddef>

namespace luz {

  using isize = std::ptrdiff_t;
  using usize = std::size_t;

} // namespace luz
#line 4 "src/cpp-template/header/rep.hpp"

#include <algorithm>

namespace luz {

  struct rep {
    struct itr {
      usize i;
      constexpr itr(const usize i) noexcept: i(i) {}
      void operator++() noexcept {
        ++i;
      }
      constexpr usize operator*() const noexcept {
        return i;
      }
      constexpr bool operator!=(const itr x) const noexcept {
        return i != x.i;
      }
    };
    const itr f, l;
    constexpr rep(const usize f, const usize l) noexcept
        : f(std::min(f, l)),
          l(l) {}
    constexpr auto begin() const noexcept {
      return f;
    }
    constexpr auto end() const noexcept {
      return l;
    }
  };

  struct rrep {
    struct itr {
      usize i;
      constexpr itr(const usize i) noexcept: i(i) {}
      void operator++() noexcept {
        --i;
      }
      constexpr usize operator*() const noexcept {
        return i;
      }
      constexpr bool operator!=(const itr x) const noexcept {
        return i != x.i;
      }
    };
    const itr f, l;
    constexpr rrep(const usize f, const usize l) noexcept
        : f(l - 1),
          l(std::min(f, l) - 1) {}
    constexpr auto begin() const noexcept {
      return f;
    }
    constexpr auto end() const noexcept {
      return l;
    }
  };

} // namespace luz
#line 2 "src/math/convolution/fast-walsh-hadamard-transform.hpp"

#line 5 "src/math/convolution/fast-walsh-hadamard-transform.hpp"

#include <cassert>
#include <vector>

namespace luz {

  template < typename T, typename F >
  void fast_walsh_hadamard_transform(std::vector< T > &f, F op) {
    const usize n = f.size();
    assert((n & (n - 1)) == 0);
    usize i = 1;
    while (i < n) {
      usize j = 0;
      while (j < n) {
        for (usize k: rep(0, i)) {
          op(f[j + k], f[j + k + i]);
        }
        j += i << 1;
      }
      i <<= 1;
    }
  }

} // namespace luz
#line 6 "src/math/convolution/bitwise-xor-convolution.hpp"

#line 9 "src/math/convolution/bitwise-xor-convolution.hpp"

namespace luz {

  template < typename T >
  std::vector< T > bitwise_xor_convolution(std::vector< T > f,
                                           std::vector< T > g) {
    assert(f.size() == g.size());

    T inv2    = T(1) / T(2);
    auto zeta = [](T &lo, T &hi) {
      T x = lo + hi;
      T y = lo - hi;
      lo  = x;
      hi  = y;
    };
    auto mobius = [inv2](T &lo, T &hi) {
      T x = lo + hi;
      T y = lo - hi;
      lo  = x * inv2;
      hi  = y * inv2;
    };

    fast_walsh_hadamard_transform(f, zeta);
    fast_walsh_hadamard_transform(g, zeta);
    for (usize i: rep(0, f.size())) {
      f[i] *= g[i];
    }
    fast_walsh_hadamard_transform(f, mobius);
    return f;
  }

} // namespace luz
#line 2 "src/math/modular-arithmetic/static-modint.hpp"

#line 2 "src/cpp-template/header/int-alias.hpp"

#include <cstdint>

namespace luz {

  using i32  = std::int32_t;
  using i64  = std::int64_t;
  using i128 = __int128_t;

  using u32  = std::uint32_t;
  using u64  = std::uint64_t;
  using u128 = __uint128_t;

} // namespace luz
#line 4 "src/math/modular-arithmetic/static-modint.hpp"

#line 6 "src/math/modular-arithmetic/static-modint.hpp"
#include <iostream>

namespace luz {

  template < u32 mod >
  class StaticPrimeModInt {
    using modint = StaticPrimeModInt;

    u32 v;

   public:
    StaticPrimeModInt(): v(0) {}

    template < typename T >
    StaticPrimeModInt(T v_) {
      i64 x = (i64)(v_ % (i64)mod);
      if (x < 0) x += mod;
      v = (u32)x;
    }

    u32 val() const {
      return v;
    }

    modint &operator+=(const modint &rhs) {
      v += rhs.v;
      if (v >= mod) v -= mod;
      return *this;
    }

    modint &operator-=(const modint &rhs) {
      v += mod - rhs.v;
      if (v >= mod) v -= mod;
      return *this;
    }

    modint &operator*=(const modint &rhs) {
      v = (u32)(u64(1) * v * rhs.v % mod);
      return *this;
    }

    modint &operator/=(const modint &rhs) {
      *this *= rhs.inverse();
      return *this;
    }

    modint operator+() const {
      return *this;
    }

    modint operator-() const {
      return modint() - *this;
    }

    friend modint operator+(const modint &lhs, const modint &rhs) {
      return modint(lhs) += rhs;
    }

    friend modint operator-(const modint &lhs, const modint &rhs) {
      return modint(lhs) -= rhs;
    }

    friend modint operator*(const modint &lhs, const modint &rhs) {
      return modint(lhs) *= rhs;
    }

    friend modint operator/(const modint &lhs, const modint &rhs) {
      return modint(lhs) /= rhs;
    }

    friend bool operator==(const modint &lhs, const modint &rhs) {
      return lhs.v == rhs.v;
    }

    friend bool operator!=(const modint &lhs, const modint &rhs) {
      return lhs.v != rhs.v;
    }

    modint pow(i64 n) const {
      assert(0 <= n);
      modint x = *this, r = 1;
      while (n) {
        if (n & 1) r *= x;
        x *= x;
        n >>= 1;
      }
      return r;
    }

    modint inverse() const {
      assert(v != 0);
      return pow(mod - 2);
    }

    static constexpr u32 get_mod() {
      return mod;
    }

    friend std::ostream &operator<<(std::ostream &os,
                                    const modint &m) {
      os << m.val();
      return os;
    }
  };

  using modint998244353  = StaticPrimeModInt< 998244353 >;
  using modint1000000007 = StaticPrimeModInt< 1000000007 >;

} // namespace luz
#line 5 "test/library-checker/bitwise_xor_convolution.test.cpp"

#line 8 "test/library-checker/bitwise_xor_convolution.test.cpp"

namespace luz {

  void main_() {
    usize n;
    std::cin >> n;

    using mint = modint998244353;
    std::vector< mint > as(1 << n);
    for (mint &a: as) {
      i32 v;
      std::cin >> v;
      a = mint(v);
    }

    std::vector< mint > bs(1 << n);
    for (mint &b: bs) {
      i32 v;
      std::cin >> v;
      b = mint(v);
    }

    auto cs = bitwise_xor_convolution(as, bs);
    for (usize i: rep(0, 1 << n)) {
      std::cout << cs[i].val()
                << (i + 1 == (usize(1) << n) ? "\n" : " ");
    }
  }

} // namespace luz

int main() {
  luz::main_();
}
Back to top page