PROBLEM LINK:Author: ravikiran0606 DIFFICULTY:EASYMEDIUM PREREQUISITES:COMBINATORICS, MATH PROBLEM:Given an equation X_{1} + X_{2} + ... + X_{N} = K and an array of N numbers a_{1},a_{2},...,a_{N}. The task is to find the number of whole number solutions satisfying the given equation such that X_{i} >= a_{i} for all i (1<=i<=N). Since the no of solutions can be large, print them modulo 10^{9} + 7. EXPLANATION:In this question, we can easily find the case for no solution that if $\displaystyle\sum_{i=1}^{N} X_i$ > K, then no solution exist for that equation. In all other conditions, we can find at least one whole number solution. In order to find the number of whole number solutions for the given equation. Let p = $\displaystyle\sum_{i=1}^{N} X_i$  K. Now our actual problem reduces to the problem of finding the no of whole number solutions in the new equation, Y_{1} + Y_{2} + ... + Y_{N} = p without any constraint. The no of solutions to the new equation is similar to the number of ways of distributing p chocolates to N children which can be done in $\binom{p+n1}{n1}$ ways. AUTHOR'S SOLUTION:Author's solution can be found here
This question is marked "community wiki".
asked 13 Mar, 23:03
