Partitions into K Groups — Solution & Editorial

Back to the Problem

The explicit formula S(N, K) = (1/K!) ∑_j=0..K (−1)^j C(K, j) (K−j)^N is O(K log N) with modular factorials.

Complexity: O(K log N)