Codeforces will not be available in the period 01:00-05:00 May, 30 (MSK, UTC +3) because of maintenance. ×

### StrawberryInsha2k's blog

By StrawberryInsha2k, history, 2 months ago, ,

Given C identical charities and N unique coins, find the number of ways of distributing the N coins to the C charities such that each charity gets at least 1, 2 or 3 coins based on input. [For a test case, this number M (1, 2 or 3) is fixed.]

T N C M

Sample Input:

3 5 3 1 5 2 2 6 2 3

Sample Output:

25 10 10

I defined dp[i][j] as the number of ways of distributing i coins to j charities. Then, a recursion relation should be derived in each of these three cases:

So for 1 at least 1 coin dp[i][j]=j∗dp[i−1][j]+dp[i−1][j−1]

I am unable to figure out the recurrence relation for at least 2 coins and at least 3 coins. Can you please explain the other two recurrence relation by clearly defining each states and transitions. I would be highly obliged to you and much of time will be saved.

Thank You

• 0

 » 2 months ago, # |   0 Sample Input ( T followed by N C M where N is the total number of unique coins and C is the number of identical charities and M is the number of coins each charity at least gets (it is either 1, 2 , 3). Sample Input : 35 3 15 2 26 2 3 Sample Output : 25 10 10