Can any one explain me the solution of the following problem->

Sam visits the most famous sweet shop in his city. The shop has an assortment of sweets of different variety. It contains a1 sweets of 1st kind, a2 sweets of 2nd kind, and so on, upto N.

Now Sam has been restricted by his mother, to select exactly S number of sweets from the shop to eat. You have to help him find out the number of ways in which he can select S sweets. Sam may have multiple queries for you and you are expected to answer them all. Input Format

First line contains integer N, such that there are N different kinds of sweets.

The following N lines represent the amount of sweets of each kind, i.e., the integer on i-th line represents the number of sweets of i-th kind.

Next line contains an integer Q, the number of queries to follow.

The following Q lines contain an integer S each, such that you have to report the number of ways in which S sweets can be selected modulo (10^9 + 7).

Output Format

The output consists of Q lines, such that each line consists of the output of the corresponding query, i.e., the number of ways in which S sweets can be selected.

Constraints

N ≤ 10^6 1 ≤ Amount of sweets of each kind ≤ 10^3 1 ≤ Q ≤ 10^4 1 ≤ S ≤ 2000

Sample Input

2

2

3

6

1

2

3

4

5

6

Sample Output

2

3

3

2

1

0

SOURCE-

an idea. N is up to 10^6, but it can be reduced to 10^3.

`for (i = 0; i < n; ++i) ++cnt[a[i]];`

.Yes, but if you want to do naive DP on each type, you need

O(S^{2}) time per type, yielding an algorithm with complexityO(S^{3}) instead ofO(NS). Not much win.You have to find coefficients of

x^{s}in (1 +x+x^{2}+ ... +x^{a1}) * (1 +x+x^{2}+ ... +x^{a2}) * ...(1 +x+x^{2}+ ... +x^{an}).We know n is very large, (1 ≤

n≤ 10^{6}), buta_{i}is not very large (0 ≤q_{i}≤ 10^{3}). We need to somehow make use of the small constraints ofa_{i}. We will have many of the terms in (1 +x+x^{2}+ ... +x^{a1}) * (1 +x+x^{2}+ ... +x^{a2}) * ...(1 +x+x^{2}+ ... +x^{an}) being same and mulitplied many times, So clubing the same together and rearraning the expression, we get (1 +x)^{c1}* (1 +x+x^{2})^{c2}* ...(1 +x+x^{2}+ ... +x^{a1000})^{c1000}.Now using the geometic progression sum, we can re-write the expression as (

x^{2}- 1)^{c1}* (x^{3}- 1)^{c2}* .. * (x^{1001}- 1)^{c1000}* (x- 1)^{ - n}Now we need to find out coefficient of

x^{k}(0 ≤k≤ 2000). Let us split the expression into two parts. First part being (x^{2}- 1)^{c1}* (x^{3}- 1)^{c2}* .. * (x^{1001}- 1)^{c1000}and second part being (x- 1)^{ - n}.We need to find coefficient of

x^{k}(0 ≤k≤ 2000) in the both the expression and later we can just muliply both the parts directly to get actual coefficients required in .Now let us focus on finding coefficients of

x^{k}in the first part only. We can do this in time using dp. Note that we can find coefficient ofx^{k}in (x^{i}- 1)^{ci}easily. All the coefficients in (x^{i}- 1)^{c}_{i}will be of only of powers ofx^{i}, coefficients of all other powers of x will be zero.Now we can do a dp for the above purpose. Let dp[i][s] denotes coefficient of s in first i terms of the given expression (

x^{2}- 1)^{c}_{1}* (x^{3}- 1)^{c}_{2}* .. * (x^{1001}- 1)^{c1000}.Now let us say we are currently at

i^{th}position in the expression (ie at (x^{i}- 1)^{ci}), we will try all multiplies ofi+ 1 as possible powers of x and will do a transition to the previous state in the dp. See the exact code for details about the transition function.Note that we are making transition per step due to which our complexity will be like where H is haromic function. As

H_{n}is bounded bylogn. We can say overall complexity is .Now let us focus to second part of the expression. How to find coefficient of

x^{k}in (x- 1)^{ - n}?. Please follow the following link for entire explanation negative exponent in binomial theoremPlease see the commented code for full understanding of the dp states.

authors solution

testers solution

[user:tourist] solution

Complexity of the entire solution is which will easily pass within the time.

P.S. If something is unclear, please point out that, I would be glad to help that out. Thank you all!!Incorrect solution in the previous edit