Donation - EDITORIAL:
Author: kishen1912000
Editorialist: kishen1912000
DIFFICULTY:
Easy
PREREQUISITES:
Dynamic Programming, Combinatorics, Stirling Numbers
PROBLEM:
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 (1, 2 or 3) is fixed.]
EXPLANATION:
Let dp[n][c] denote the number of ways of distributing n coins to c charities. Then, a recursion relation can be derived in each of these cases:
At least 1 coin each:
dp[n][c] = c*dp[n-1][c] + dp[n-1][c-1]
Where, the first term denotes the number of ways of distributing n-1 coins to c charities and then distribute the n^{th} to any one, which can be done in c ways. The second term denotes the number of ways of distributing n-1 coins to c-1 charities and the n^{th} coin is given to the c^{th} charity.
Similarly, we get the following recurrence relations in the other two cases:
At least 2 coins each:
dp[n][c] = c*dp[n-1][c] + (n-1)*dp[n-2][c-1]
At least 3 coins each:
dp[n][c] = c*dp[n-1][c] + \binom{n-1}{2}*dp[n-3][c-1]
The final answer required in each case is dp[N][C]. As the number is huge, use modular arithmetic appropriately where required.
Time Complexity:
O(T\times N\times C)
SOLUTIONS:
Setter's Solution
M = 10**9+7
def choose(n,k):
if k==1:
return n
elif k==2:
return (n*(n-1)//2)%M
else:
return 1
for _ in range(int(input())):
n,c,q = [int(s) for s in input().split()]
dp = [[0 for i in range(c+1)] for j in range(n+1)]
for i in range(1,n+1):
dp[i][1] = 0 if i<q else 1
for j in range(2,c+1):
for i in range(j*q,n+1):
dp[i][j] = ((choose(i-1,q-1)*dp[i-q][j-1])%M + (j*dp[i-1][j])%M)%M
print(dp[n][c])