test/zeta_transform.test.cpp

• View this file on GitHub
• Last update: 2020-03-11 23:32:43+09:00
• Problem: http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=3119

Depends on

• Superset Möbius Transform (algorithm/superset_mobius_transform.cpp)
• Superset Zeta Transform (algorithm/superset_zeta_transform.cpp)
• other/fast_ios.cpp
• other/int_alias.cpp
• other/modint.cpp
• other/multiplies_monoid.cpp
• other/plus_group.cpp

Code

#define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=3119"

#include "algorithm/superset_mobius_transform.cpp"
#include "algorithm/superset_zeta_transform.cpp"
#include "other/modint.cpp"
#include "other/multiplies_monoid.cpp"
#include "other/plus_group.cpp"

#include <iostream>

int main() {
#include "other/fast_ios.cpp"

  using mint = modint<1000000007>;
  constexpr int b = 20;

  int n;
  std::cin >> n;
  std::vector<mint> v(1 << b, 1);
  for (int i = 0; i != n; i += 1) {
    int a;
    std::cin >> a;
    v[a] *= 2;
  }
  superset_zeta_transform<multiplies_monoid<mint>>(v);
  for (mint &e : v)
    e -= 1;
  superset_mobius_transform<plus_group<mint>>(v);
  std::cout << v[0].value() << "\n";
}

#line 1 "test/zeta_transform.test.cpp"
#define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=3119"

#line 2 "other/int_alias.cpp"

#include <cstddef>
#include <cstdint>

using i32 = std::int32_t;
using i64 = std::int64_t;
using u32 = std::uint32_t;
using u64 = std::uint64_t;
using isize = std::ptrdiff_t;
using usize = std::size_t;
#line 2 "algorithm/superset_mobius_transform.cpp"

#include <vector>

template <class G>
void superset_mobius_transform(std::vector<typename G::value_type> &a) {
  const usize n = a.size();
  usize i = 1;
  while (i < n)
    i *= 2;
  while (i != 1) {
    i /= 2;
    for (usize j = 0; j != n; j += 1) {
      if ((j & i) != 0)
        a[j & ~i] = G::operation(a[j & ~i], G::inverse(a[j]));
    }
  }
}

/**
 * @brief Superset Möbius Transform
 */
#line 2 "algorithm/superset_zeta_transform.cpp"

#line 4 "algorithm/superset_zeta_transform.cpp"

template <class S>
void superset_zeta_transform(std::vector<typename S::value_type> &a) {
  const usize n = a.size();
  for (usize i = 1; i < n; i *= 2) {
    for (usize j = 0; j != n; j += 1) {
      if ((j & i) != 0)
        a[j & ~i] = S::operation(a[j & ~i], a[j]);
    }
  }
}

/**
 * @brief Superset Zeta Transform
 */
#line 2 "other/modint.cpp"

template <std::uint_fast64_t Modulus> class modint {
  using u64 = std::uint_fast64_t;

public:
  using value_type = u64;

  static constexpr u64 mod = Modulus;

private:
  static_assert(mod < static_cast<u64>(1) << 32,
                "Modulus must be less than 2**32");

  u64 v;

  constexpr modint &negate() noexcept {
    if (v != 0)
      v = mod - v;
    return *this;
  }

public:
  constexpr modint(const u64 x = 0) noexcept : v(x % mod) {}
  constexpr u64 &value() noexcept { return v; }
  constexpr const u64 &value() const noexcept { return v; }
  constexpr modint operator+() const noexcept { return modint(*this); }
  constexpr modint operator-() const noexcept { return modint(*this).negate(); }
  constexpr modint operator+(const modint rhs) const noexcept {
    return modint(*this) += rhs;
  }
  constexpr modint operator-(const modint rhs) const noexcept {
    return modint(*this) -= rhs;
  }
  constexpr modint operator*(const modint rhs) const noexcept {
    return modint(*this) *= rhs;
  }
  constexpr modint operator/(const modint rhs) const noexcept {
    return modint(*this) /= rhs;
  }
  constexpr modint &operator+=(const modint rhs) noexcept {
    v += rhs.v;
    if (v >= mod)
      v -= mod;
    return *this;
  }
  constexpr modint &operator-=(const modint rhs) noexcept {
    if (v < rhs.v)
      v += mod;
    v -= rhs.v;
    return *this;
  }
  constexpr modint &operator*=(const modint rhs) noexcept {
    v = v * rhs.v % mod;
    return *this;
  }
  constexpr modint &operator/=(modint rhs) noexcept {
    u64 exp = mod - 2;
    while (exp != 0) {
      if (exp % 2 != 0)
        *this *= rhs;
      rhs *= rhs;
      exp /= 2;
    }
    return *this;
  }
};
template <std::uint_fast64_t Modulus>
constexpr typename modint<Modulus>::u64 modint<Modulus>::mod;
#line 1 "other/multiplies_monoid.cpp"
template <class T> class multiplies_monoid {
public:
  using value_type = T;
  static constexpr T operation(const T &l, const T &r) noexcept {
    return l * r;
  }
  static constexpr T identity = 1;
};
#line 1 "other/plus_group.cpp"
template <class T> class plus_group {
public:
  using value_type = T;
  static constexpr T operation(const T &l, const T &r) noexcept {
    return l + r;
  }
  static constexpr T identity = 0;
  static constexpr T inverse(const T &x) noexcept { return -x; }
};
#line 8 "test/zeta_transform.test.cpp"

#include <iostream>

int main() {
#line 1 "other/fast_ios.cpp"
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
#line 13 "test/zeta_transform.test.cpp"

  using mint = modint<1000000007>;
  constexpr int b = 20;

  int n;
  std::cin >> n;
  std::vector<mint> v(1 << b, 1);
  for (int i = 0; i != n; i += 1) {
    int a;
    std::cin >> a;
    v[a] *= 2;
  }
  superset_zeta_transform<multiplies_monoid<mint>>(v);
  for (mint &e : v)
    e -= 1;
  superset_mobius_transform<plus_group<mint>>(v);
  std::cout << v[0].value() << "\n";
}

Back to top page