This documentation is automatically generated by online-judge-tools/verification-helper
View the Project on GitHub noshi91/Library
#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"; }