PROBLEM LINK:Author: Gerald Agapov DIFFICULTY:Medium PREREQUISITES:Dynamic Programming, Combinatorics PROBLEM: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. EXPLANATION: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 x_{1} + x_{2} + ... + x_{n} = m, where 0 <= x_{i}. 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[i][j] to stand for the number of different multisets which contain the objects with rang between 1 and i and their rangsum is j. The update rule is like the following:
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). AUTHOR'S AND TESTER'S SOLUTIONS:Author's solution can be found here.
This question is marked "community wiki".
asked 23 Dec '13, 00:15

I dont know why they even write editorials like this! I do not understand it ! Not written clearly , when turning to author and tester's code, they have used so many Pre processor directives ! Are they writing these codes for us or are they playing!! answered 09 Jun '15, 13:52

can u please explain  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). answered 26 Feb '16, 17:49
