PROBLEM LINK:
Author: ravikiran0606
Editorialist: ravikiran0606
DIFFICULTY:
EASY-MEDIUM
PREREQUISITES:
COMBINATORICS, MATH
PROBLEM:
Given an equation X1 + X2 + … + XN = K and an array of N numbers a1,a2,…,aN. The task is to find the number of whole number solutions satisfying the given equation such that Xi >= ai for all i (1<=i<=N). Since the no of solutions can be large, print them modulo 109 + 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, Y1 + Y2 + … + YN = 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+n-1}{n-1} ways.
AUTHOR’S SOLUTION:
Author’s solution can be found here