11723. Combinations with repetitions
Find the number of ways to distribute n identical objects among k distinct positions, where each
position can hold any number of objects
Input. Two positive integers k and n (k, n ≤ 100).
Output. Print the number of ways to distribute the objects modulo 109 + 7.
|
Sample input 1 |
Sample output
1 |
|
3 4 |
15 |
|
|
|
|
Sample input 2 |
Sample output
2 |
|
3 2 |
6 |
SOLUTION
combinatorics
Algorithm analysis
This problem reduces to
computing the number of combinations with repetition, which corresponds to
counting the number of solutions of the equation:
x1 + x2 + ...+ xk = n,
where
·
xi is the number of objects placed in the i-th
position,
·
k is the number of positions.
·
n is the total number of objects.
Each xi can be any non-negative
integer. The number of solutions of this equation is given by the formula (see
e-olymp problem 11551): 
.
Example
In the first example (k
= 3, n = 4), the
answer is 
= 
= 15.
In the second example (k
= 3, n = 2), the answer is 
= 
= 6.
Algorithm implementation
Let us define the constants and the dp array for storing the values
of the binomial coefficients.
#define MAX 201
#define MOD 1000000007
long long dp[MAX][MAX];
The function Cnk computes the value of the binomial
coefficient 
modulo
MOD = 109
+ 7.
long long Cnk(int n, int k)
{
if (n == k) return 1;
if (k == 0) return 1;
if (dp[n][k] != -1) return dp[n][k];
return dp[n][k] = (Cnk(n - 1, k - 1) + Cnk(n - 1, k)) % MOD;
}
The main part of the program. Read the input data.
scanf("%d %d", &k, &n);
memset(dp,
-1, sizeof(dp));
Compute and print the answer 
.
printf("%lld\n", Cnk(n + k - 1, k - 1));