Subset sum problem (Count, FPS)
(Mylib/Typical/subset_sum_count_fps.cpp)

• View this file on GitHub
• Last update: 2021-04-23 23:44:44+09:00
• Link: View error logs on GitHub Actions

Operations

Requirements

Notes

Problems

References

Verified with

• test/yosupo-judge/sharp_p_subset_sum/main.test.cpp

Code

#pragma once
#include <vector>

namespace haar_lib {
  template <typename Fps>
  auto subset_sum_count_fps(std::vector<int> s, int t) {
    using T = typename Fps::value_type;

    std::vector<int> c(t + 1);
    for (int i : s) c[i] += 1;

    Fps ret(t + 1);

    for (int i = 1; i <= t; ++i) {
      if (c[i] == 0) continue;

      for (int j = 1; j * i <= t; ++j) {
        const int k = j * i;
        const T x   = (j % 2 == 1 ? 1 : -1) * i * ((T) k).inv();
        ret[k] += x * c[i];
      }
    }

    ret = ret.exp();

    return ret;
  }
}  // namespace haar_lib

#line 2 "Mylib/Typical/subset_sum_count_fps.cpp"
#include <vector>

namespace haar_lib {
  template <typename Fps>
  auto subset_sum_count_fps(std::vector<int> s, int t) {
    using T = typename Fps::value_type;

    std::vector<int> c(t + 1);
    for (int i : s) c[i] += 1;

    Fps ret(t + 1);

    for (int i = 1; i <= t; ++i) {
      if (c[i] == 0) continue;

      for (int j = 1; j * i <= t; ++j) {
        const int k = j * i;
        const T x   = (j % 2 == 1 ? 1 : -1) * i * ((T) k).inv();
        ret[k] += x * c[i];
      }
    }

    ret = ret.exp();

    return ret;
  }
}  // namespace haar_lib

Back to top page