You are not logged in. Please login at www.codechef.com to post your questions!

×

# RKABOL04 - Editorial

Author: ravikiran0606
Editorialist: ravikiran0606

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

This question is marked "community wiki".

asked 13 Mar, 23:03

41
accept rate: 0%

19.3k348495534

 toggle preview community wiki:
Preview

### Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×15,006
×1,487
×768
×19
×19
×19

question asked: 13 Mar, 23:03

question was seen: 122 times

last updated: 15 Mar, 13:37