Partition Number
(library/sequence/partition_number.hpp)

• View this file on GitHub
• Last update: 2022-07-21 04:00:33+09:00
• Include: #include "library/sequence/partition_number.hpp"

Partition Number

partition_number

• シグネチャ

  template <typename mint>
  std::vector<mint> partition_number(int n)
  

• 概要

  分割数 $P_0,\ldots,P_N$ を計算します．ここで，$P_i$ は，正整数を要素とする多重集合であって，総和が $i$ であるようなものの個数と一致します．

  母関数は $\displaystyle \sum_{i=0} ^ \infty P_i x ^ i=\prod_{k=1} ^ \infty \dfrac{1}{1-x ^ k}$ で表され，オイラーの五角数定理 :

  \[\prod_{k=1} ^ \infty(1-x ^ k)=\sum_{k=-\infty} ^ \infty(-1) ^ k x ^ {k(3k-1)/2}\]

  を用いることで，

  \[\begin{aligned} \sum_{i=0} ^ n P_i x ^ i &=\left(1+\sum_{k=1} ^ n (-1) ^ k \Bigl(x ^ {k(3k-1)/2}+x ^ {k(3k+1)/2}\Bigr)\right) ^ {-1}\bmod x ^ {n+1} \end{aligned}\]

  により計算できます．

• テンプレート引数

  • mint: modint 型を想定

• 返り値

  分割数 $\{P_i\} _ {i=0} ^ N$

• 制約

  • $0\leq n\leq 10 ^ 6$

• 時間計算量

  $O(n\log n)$

• 参考

  • (形式的)べき級数と数え上げの写像12相との関係性　後編

Verified with

• test/src/sequence/partition_number/partition_function.test.cpp
• test/src/sequence/partition_number/partition_function_2.test.cpp

Code

#ifndef SUISEN_PARTITON_NUMBER
#define SUISEN_PARTITON_NUMBER

#include <vector>

namespace suisen {
    template <typename FPSType>
    std::vector<typename FPSType::value_type> partition_number(int n) {
        FPSType inv(n + 1);
        inv[0] = 1;
        for (int i = 1, k = 1; k <= n; k += 3 * i + 1, i++) {
            if (i & 1) --inv[k];
            else ++inv[k];
        }
        for (int i = 1, k = 2; k <= n; k += 3 * i + 2, i++) {
            if (i & 1) --inv[k];
            else ++inv[k];
        }
        inv.inv_inplace(n + 1), inv.resize(n + 1);
        return inv;
    }
} // namespace suisen

#endif // SUISEN_PARTITON_NUMBER

#line 1 "library/sequence/partition_number.hpp"



#include <vector>

namespace suisen {
    template <typename FPSType>
    std::vector<typename FPSType::value_type> partition_number(int n) {
        FPSType inv(n + 1);
        inv[0] = 1;
        for (int i = 1, k = 1; k <= n; k += 3 * i + 1, i++) {
            if (i & 1) --inv[k];
            else ++inv[k];
        }
        for (int i = 1, k = 2; k <= n; k += 3 * i + 2, i++) {
            if (i & 1) --inv[k];
            else ++inv[k];
        }
        inv.inv_inplace(n + 1), inv.resize(n + 1);
        return inv;
    }
} // namespace suisen

Back to top page