Partition number (Enumerate $P(n, n)$)
(Mylib/Combinatorics/partition_number_n.cpp)

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

Operations

• partition_number(int n)
  • $P(0)$ ~ $P(n)$を列挙する。
  • Time complexity $O(n\sqrt{n})$

Requirements

Notes

Problems

• Partition Function

References

Verified with

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

Code

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

namespace haar_lib {
  template <typename T>
  std::vector<T> partition_number_n(int N) {
    std::vector<T> p(N + 1);

    p[0] = 1;

    for (int i = 1; i <= N; ++i) {
      int s = std::sqrt(1 + 24 * i);

      for (int j = 1; j <= (s + 1) / 6; ++j) {
        p[i] += p[i - j * (3 * j - 1) / 2] * (j % 2 ? 1 : -1);
      }

      for (int j = 1; j <= (s - 1) / 6; ++j) {
        p[i] += p[i - j * (3 * j + 1) / 2] * (j % 2 ? 1 : -1);
      }
    }

    return p;
  }
}  // namespace haar_lib

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

namespace haar_lib {
  template <typename T>
  std::vector<T> partition_number_n(int N) {
    std::vector<T> p(N + 1);

    p[0] = 1;

    for (int i = 1; i <= N; ++i) {
      int s = std::sqrt(1 + 24 * i);

      for (int j = 1; j <= (s + 1) / 6; ++j) {
        p[i] += p[i - j * (3 * j - 1) / 2] * (j % 2 ? 1 : -1);
      }

      for (int j = 1; j <= (s - 1) / 6; ++j) {
        p[i] += p[i - j * (3 * j + 1) / 2] * (j % 2 ? 1 : -1);
      }
    }

    return p;
  }
}  // namespace haar_lib

Back to top page