Library Checker「Partition Function」

形式的冪級数を用いた解法について書きます．もっと高速な解法もあるようですが，~~わかんないです．~~ maspyさんに教えていただきました．この記事の最後で説明しています．

問題概要

$0, 1, \dots, N$ の分割数をそれぞれ求めてください．

judge.yosupo.jp

分割数について

ja.wikipedia.org

分割数は，総和が $N$ である正の整数の多重集合の個数といえます．もうちょっと簡単に言うと，1円硬貨，2円硬貨，3円硬貨…が無限枚あるときにピッタリ $N$ 円を払う方法の個数です．

解き方

それぞれの硬貨を何枚使うか？に着目します．明らかにN円硬貨より大きい硬貨を使うことはありません．なので，以降は1円硬貨，2円硬貨，3円硬貨，…，N円硬貨が無限枚あるとして考えます．

1円硬貨を何枚か使うとき，0円，1円，2円…が払えて，2円硬貨を使うとき，0円，2円，4円…が払えます．以降も同様に考えていくと，結局形式的冪級数 $f = (1+x+x^{2} + \dots)(1 + x^{2} + x^{4} + \dots) \dots (1 + x^{N} + \dots)$ の $N$ 次までの係数を求めることができればよいことがわかります． $N$ 次以降の項を適当に切ってしまえば， $N$ 次の多項式の積になるのですが， $N$ 次の式が $N$ 個出てくるので，そのまま計算するのはしんどいです．

これは，等比数列の形になっているので， $\displaystyle f = \frac{1}{1 - x} \times \frac{1}{1 - x^{2}} \times \dots \times \frac{1}{1 - x^{N}}$ として変形できます．

これを計算するために，俗にexp-log典型と呼ばれるテクニックを使います．

exp-log典型

$f = \exp(\log(f))$ という性質を用います． $\displaystyle \log(f) =\log( \frac{1}{1 - x}) + \log(\frac{1}{1 - x^{2}}) + \dots + \log(\frac{1}{1 - x^{N}})$ であり，logの性質から

$\displaystyle \log(f) =- \log( {1 - x}) - \log({1 - x^{2}}) - \dots - \log({1 - x^{N}})$ として求めることができます．

ここで， $\log(1 - t)$ のマクローリン展開を考えると， $\displaystyle \log(1 - t) = -t-\frac{t^{2}}{2}-\frac{t^{3}}{3} \dots$ となります．

さて， $k = 1, 2, \dots, N$ について $-\log({1 - x^{k}})$ のマクローリン展開したやつ $\displaystyle -\log(1 - x^{k}) = x^{k}+\frac{ x^{2k}}{2}+\frac{x^{3k}}{3} \dots$ を足し合わせていけばよいです．この式を計算する際， $N$ 次以降は切ってよいことから，いわゆる調和級数のやつで足し合わせる項の個数は $O(N \log N)$ になります．