説明

$n$ を順序を区別せずに自然数の和に分ける場合の数を $n$ の分割数 $p(n)$ と呼ぶ。

例えば $p(0) = 1$, $p(1) = 1$ ($1$), $p(2) = 2$ ($2, 1+1$), $p(3) = 3$ ($3, 2+1, 1+1+1$)

分割数の母関数は次のとおりである。

$ \displaystyle \sum_{n=0}^{\infty} p(n) t^n = \prod_{k=1}^{\infty} \frac {1} {1 - t^k} = \frac {1} {\prod_{k=1}^{\infty} {(1 - t^k)} }$

このままだとあまり役に立たないんですが, オイラーの五角数定理(Euler’s pentagonal number theorem) を使うといい感じに計算できる。

オイラーの五角数定理では次を示す。

$ \displaystyle {\prod_{k=1}^{\infty} {(1 - t^k)} = 1 + \sum_{k=1}^{\infty} (-1)^{k} (x^{k(3k+1)/2}+x^{k(3k-1)/2})}$

この逆数を計算できれば良くて, FFTにより $O(n \log n)$ で計算できる。

計算量

  • $O(n \log n)$

実装例

依存ライブラリ Polynominal-Mod

  • partition($n$): $[0, n]$ の分割数を返す。
template< typename T >
FormalPowerSeries< T > partition(int N) {
  FormalPowerSeries< T > po(N + 1);
  po[0] = 1;
  for(int k = 1; k <= N; k++) {
    if(1LL * k * (3 * k + 1) / 2 <= N) po[k * (3 * k + 1) / 2] += (k % 2 ? -1 : 1);
    if(1LL * k * (3 * k - 1) / 2 <= N) po[k * (3 * k - 1) / 2] += (k % 2 ? -1 : 1);
  }
  return po.inv();
}