Dynamic Programming, Combinatorics
Given a lot of objects, grouped by the positive rang. F(N) determines the number of different object with rang N. Find out the number of different multisets whose sum of rangs are S.
First of all, we need to solve this basic problem: there are n different types of objects. Each object has infinity copies. How many different multisets which contains exactly m objects. (Denote this solution as G(n, m))
This problem is equivalent to the number of integer solutions of the equation x1 + x2 + … + xn = m, where 0 <= xi.
We can plus n on both sides of the equation. And then, every solution is equivalent to insert n - 1 break points into m + n -1 gaps. Therefore, the answer is C(m + n - 1, n - 1). Here C is the Combination function.
Based on this, we can solve this problem using dynamic programming. Use f*[j] to stand for the number of different multisets which contain the objects with rang between 1 and i and their rang-sum is j. The update rule is like the following:
f*[j] * G(F(i + 1), k) ---> f[i + 1][j + k * (i + 1)]
Since the modulo is a prime, we can perform the integer division via some multiplication (based on the Fermat’s little theorem, which is a special case of Euler Theorem). And also, k is small here. we can calculate the G(,) function in O(k) time. Because (S / 1)^2 + (S / 2)^2 + (S / 3)^2 + … (S / S)^2 is in O((logS)^2), the total time complexity is O(S^2(logS)^2).