This documentation is automatically generated by online-judge-tools/verification-helper
View the Project on GitHub suisen-cp/cp-library-cpp
#include "library/polynomial/subset_sum.hpp"
#ifndef SUISEN_SUBSET_SUM #define SUISEN_SUBSET_SUM #include <vector> #include "library/math/inv_mods.hpp" namespace suisen { template <typename FPSType> std::vector<typename FPSType::value_type> subset_sum(const int n, const std::vector<int>& items) { using mint = typename FPSType::value_type; std::vector<int> a(n + 1, 0); for (int e : items) { assert(e >= 0); if (e <= n) ++a[e]; } inv_mods<mint> invs(n); FPSType log(n + 1); for (int i = 1; i <= n; ++i) { if (a[i] == 0) continue; for (int j = 1; i * j <= n; ++j) { if (j & 1) log[i * j] += invs[j] * a[i]; else log[i * j] -= invs[j] * a[i]; } } log.exp_inplace(n + 1), log.resize(n + 1); mint p = mint(2).pow(a[0]); for (mint& e : log) e *= p; return log; } } // namespace suisen #endif // SUISEN_SUBSET_SUM
#line 1 "library/polynomial/subset_sum.hpp" #include <vector> #line 1 "library/math/inv_mods.hpp" #line 5 "library/math/inv_mods.hpp" namespace suisen { template <typename mint> class inv_mods { public: inv_mods() = default; inv_mods(int n) { ensure(n); } const mint& operator[](int i) const { ensure(i); return invs[i]; } static void ensure(int n) { int sz = invs.size(); if (sz < 2) invs = { 0, 1 }, sz = 2; if (sz < n + 1) { invs.resize(n + 1); for (int i = sz; i <= n; ++i) invs[i] = mint(mod - mod / i) * invs[mod % i]; } } private: static std::vector<mint> invs; static constexpr int mod = mint::mod(); }; template <typename mint> std::vector<mint> inv_mods<mint>::invs{}; template <typename mint> std::vector<mint> get_invs(const std::vector<mint>& vs) { const int n = vs.size(); mint p = 1; for (auto& e : vs) { p *= e; assert(e != 0); } mint ip = p.inv(); std::vector<mint> rp(n + 1); rp[n] = 1; for (int i = n - 1; i >= 0; --i) { rp[i] = rp[i + 1] * vs[i]; } std::vector<mint> res(n); for (int i = 0; i < n; ++i) { res[i] = ip * rp[i + 1]; ip *= vs[i]; } return res; } } #line 7 "library/polynomial/subset_sum.hpp" namespace suisen { template <typename FPSType> std::vector<typename FPSType::value_type> subset_sum(const int n, const std::vector<int>& items) { using mint = typename FPSType::value_type; std::vector<int> a(n + 1, 0); for (int e : items) { assert(e >= 0); if (e <= n) ++a[e]; } inv_mods<mint> invs(n); FPSType log(n + 1); for (int i = 1; i <= n; ++i) { if (a[i] == 0) continue; for (int j = 1; i * j <= n; ++j) { if (j & 1) log[i * j] += invs[j] * a[i]; else log[i * j] -= invs[j] * a[i]; } } log.exp_inplace(n + 1), log.resize(n + 1); mint p = mint(2).pow(a[0]); for (mint& e : log) e *= p; return log; } } // namespace suisen