Partition number (FPS)
(Mylib/Combinatorics/partition_number_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/partition_function/main.fps.test.cpp

Code

#pragma once
#include <cmath>
#include <vector>

namespace haar_lib {
  template <typename Fps>
  Fps partition_number_fps(int N) {
    using T = typename Fps::value_type;

    std::vector<T> f(N + 1);
    f[0] = 1;

    {
      const int M = (std::sqrt(1 + 24 * N) - 1) / 6;
      for (int i = 1; i <= M; ++i) {
        f[i * (3 * i + 1) / 2] += (i % 2 == 0 ? 1 : -1);
      }
    }

    {
      const int M = (std::sqrt(1 + 24 * N) + 1) / 6;
      for (int i = 1; i <= M; ++i) {
        f[i * (3 * i - 1) / 2] += (i % 2 == 0 ? 1 : -1);
      }
    }

    Fps ret(f);
    ret = ret.inv();

    return ret;
  }
}  // namespace haar_lib

#line 2 "Mylib/Combinatorics/partition_number_fps.cpp"
#include <cmath>
#include <vector>

namespace haar_lib {
  template <typename Fps>
  Fps partition_number_fps(int N) {
    using T = typename Fps::value_type;

    std::vector<T> f(N + 1);
    f[0] = 1;

    {
      const int M = (std::sqrt(1 + 24 * N) - 1) / 6;
      for (int i = 1; i <= M; ++i) {
        f[i * (3 * i + 1) / 2] += (i % 2 == 0 ? 1 : -1);
      }
    }

    {
      const int M = (std::sqrt(1 + 24 * N) + 1) / 6;
      for (int i = 1; i <= M; ++i) {
        f[i * (3 * i - 1) / 2] += (i % 2 == 0 ? 1 : -1);
      }
    }

    Fps ret(f);
    ret = ret.inv();

    return ret;
  }
}  // namespace haar_lib

Back to top page