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(S2) time per type, yielding an algorithm with complexity O(S3) instead of O(NS). Not much win.
You have to find coefficients of xs in (1 + x + x2 + ... + xa1) * (1 + x + x2 + ... + xa2) * ...(1 + x + x2 + ... + xan).
We know n is very large, (1 ≤ n ≤ 106), but ai is not very large (0 ≤ qi ≤ 103). We need to somehow make use of the small constraints of ai. We will have many of the terms in (1 + x + x2 + ... + xa1) * (1 + x + x2 + ... + xa2) * ...(1 + x + x2 + ... + xan) being same and mulitplied many times, So clubing the same together and rearraning the expression, we get (1 + x)c1 * (1 + x + x2)c2 * ...(1 + x + x2 + ... + xa1000)c1000.
Now using the geometic progression sum, we can re-write the expression as (x2 - 1)c1 * (x3 - 1)c2 * .. * (x1001 - 1)c1000 * (x - 1) - n
Now we need to find out coefficient of xk (0 ≤ k ≤ 2000). Let us split the expression into two parts. First part being (x2 - 1)c1 * (x3 - 1)c2 * .. * (x1001 - 1)c1000 and second part being (x - 1) - n.
We need to find coefficient of xk (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 xk in the first part only. We can do this in
time using dp. Note that we can find coefficient of xk in (xi - 1)ci easily. All the coefficients in (xi - 1)ci will be of only of powers of xi, 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 (x2 - 1)c1 * (x3 - 1)c2 * .. * (x1001 - 1)c1000.
Now let us say we are currently at ith position in the expression (ie at (xi - 1)ci), we will try all multiplies of i + 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 Hn is bounded by logn. We can say overall complexity is 
.
Now let us focus to second part of the expression. How to find coefficient of xk in (x - 1) - n ?. Please follow the following link for entire explanation negative exponent in binomial theorem
Please see the commented code for full understanding of the dp states.
which will easily pass within the time.
authors solution
testers solution
[user:tourist] solution
Complexity of the entire solution is
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