$\#_p$ Subset Sum
(src/polynomial/subset_sum.hpp)

• View this file on GitHub
• Last update: 2024-05-22 00:21:24+09:00
• Include: #include "src/polynomial/subset_sum.hpp"

入力

$N$ 個の非負整数 $s _ 0, \dots , s _ {N - 1}$ 及び正整数 $m$．

出力

$t = 1, \dots , m$ について $\sum _ {i \in I} s _ i = t$ となる $I \subseteq \lbrace 0, 1, \dots , N - 1 \rbrace$ の個数．

計算量

時間計算量 $\mathrm{O}(N + M \log M)$

概要

$s _ i = 0$ については答えを $2$ 倍すれば良いから以降は $s _ i \geq 1$ とする． $t$ に対する答えは

\[[x ^ t] \prod _ {i = 0} ^ {N - 1} (1 + x ^ {s _ i}) = \exp \left( \sum _ {i = 0} ^ {N - 1} \log (1 + x ^ {s _ i}) \right)\]

に等しい．

ここで，

\[\log (1 + x) = x - \frac{x ^ 2}{2} + \frac{x ^ 3}{3} - \cdots = \sum _ {i \geq 1} \frac{(-1) ^ {i - 1}}{i} x ^ i\]

であるから $s _ i = k$ なる $i \in \lbrace 0, 1, \dots , N - 1 \rbrace$ の個数を $c _ k\ (k \in \lbrack 1, m \rbrack)$ とすると，

\[\sum _ {i = 0} ^ {N - 1} \log (1 + x ^ {s _ i}) = \sum _ {k = 1} ^ m c_k \sum _ {k i \leq m} \frac{(-1) ^ {i - 1}}{i} x^{k i}\]

で，これは $\mathrm{O}(M \log M)$ 時間で計算可能である．

Links

Depends on

• Formal Power Series (src/polynomial/FormalPowerSeries.hpp)

Verified with

• test/yosupo/sharp_p_subset_sum.test.cpp

Code

#pragma once
#include <vector>
#include "FormalPowerSeries.hpp"

template <typename T> std::vector<T> subset_sum(const std::vector<int>& s, int m) {
    std::vector<int> cnt(m + 1, 0);
    for (const int& x : s) {
        assert(x >= 0);
        if (x <= m) cnt[x]++;
    }
    FormalPowerSeries<T> res(m + 1);
    std::vector<T> inv(m + 1);
    inv[0] = T(0);
    if (m > 0) inv[1] = T(1);
    auto mod = T::mod();
    for (int i = 2; i <= m; i++) inv[i] = -inv[mod % i] * (mod / i);
    for (int i = 1; i <= m; i++) {
        if (cnt[i] == 0) continue;
        for (int j = 1; i * j <= m; j++) {
            if (j & 1)
                res[i * j] += inv[j] * cnt[i];
            else
                res[i * j] -= inv[j] * cnt[i];
        }
    }
    res = res.exp(m + 1);
    T p = T(2).pow(cnt[0]);
    for (auto& val : res) val *= p;
    return res;
}

Traceback (most recent call last):
  File "/opt/hostedtoolcache/Python/3.13.3/x64/lib/python3.13/site-packages/onlinejudge_verify/documentation/build.py", line 71, in _render_source_code_stat
    bundled_code = language.bundle(stat.path, basedir=basedir, options={'include_paths': [basedir]}).decode()
                   ~~~~~~~~~~~~~~~^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  File "/opt/hostedtoolcache/Python/3.13.3/x64/lib/python3.13/site-packages/onlinejudge_verify/languages/cplusplus.py", line 187, in bundle
    bundler.update(path)
    ~~~~~~~~~~~~~~^^^^^^
  File "/opt/hostedtoolcache/Python/3.13.3/x64/lib/python3.13/site-packages/onlinejudge_verify/languages/cplusplus_bundle.py", line 401, in update
    self.update(self._resolve(pathlib.Path(included), included_from=path))
    ~~~~~~~~~~~^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  File "/opt/hostedtoolcache/Python/3.13.3/x64/lib/python3.13/site-packages/onlinejudge_verify/languages/cplusplus_bundle.py", line 401, in update
    self.update(self._resolve(pathlib.Path(included), included_from=path))
    ~~~~~~~~~~~^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  File "/opt/hostedtoolcache/Python/3.13.3/x64/lib/python3.13/site-packages/onlinejudge_verify/languages/cplusplus_bundle.py", line 401, in update
    self.update(self._resolve(pathlib.Path(included), included_from=path))
                ~~~~~~~~~~~~~^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  File "/opt/hostedtoolcache/Python/3.13.3/x64/lib/python3.13/site-packages/onlinejudge_verify/languages/cplusplus_bundle.py", line 260, in _resolve
    raise BundleErrorAt(path, -1, "no such header")
onlinejudge_verify.languages.cplusplus_bundle.BundleErrorAt: atcoder/convolution.hpp: line -1: no such header

Back to top page