### PROBLEM LINK:

**Author:** Gerald Agapov

**Tester:** Tasnim Imran Sunny

**Editorialist:** Jingbo Shang

### 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 *rang*s 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*[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**).

### AUTHOR’S AND TESTER’S SOLUTIONS:

Author’s solution can be found here.

Tester’s solution can be found here.