Subset Sum
(library/polynomial/subset_sum.hpp)

• View this file on GitHub
• Last update: 2023-07-09 04:04:16+09:00
• Include: #include "library/polynomial/subset_sum.hpp"

Subset Sum

Depends on

• 逆元テーブル (library/math/inv_mods.hpp)

Verified with

• test/src/polynomial/subset_sum/p_subset_sum.test.cpp
• test/src/polynomial/subset_sum/p_subset_sum_2.test.cpp

Code

#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

Back to top page