Find the nth partition number mod p in O(n log n)

This algorithm comes from a study of subset sum [1]. exp, log, recip are described in [2].

The generating function of partition number is

\[ (1+x+x^2+\cdots)(1+x^2+x^4+\cdots)(1+x^3+x^6+\cdots)\cdots. \]

The logarithm of this function is

\[ -\log(1-x)-\log(1-x^2)-\log(1-x^3)-\cdots. \]

Thus, we can compute the nth partition like [1]. The entire source code is
https://ideone.com/bJzgj8. For simplicity, O(n^2) multiplication is used in it. Needless to say, #knapsack with repetition can also be solved in the same way.





[1] Ce Jin, Hongxun Wu. A Simple Near-Linear Pseudopolynomial Time Randomized Algorithm for Subset Sum, https://arxiv.org/abs/1807.11597 .
[2] R. P. Brent. Multiple-precision zero-finding methods and the complexity of elementary function evaluation, https://arxiv.org/abs/1004.3412 .