Computing a specific coefficient in a product of polynomials Generator functions

This gives the context for why this challenge came to life. Feel free to ignore.

Generator functions are a nice way of encoding the solution to a problem of combinatorics. You just write some polynomials, multiply them and then your solution is the coefficient of one of the terms.

For example, how many bouquets of 10 flowers can you make if you want to use 3 or more dandelions, really want to use an even number of lilies and cannot afford more than 5 roses? Easy, just find the coefficient of x^10 in

$$(x^3 + x^4 + x^5 + x^6 + x^7 + x^8 + x^9 + x^{10})\times(1 + x^2 + x^4 + x^6 + x^8 + x^{10})\times(1 + x + x^2 + x^3 + x^4 + x^5)$$

Task

Compute a specific coefficient from a product of polynomials.

Example

If k = 3 and the product given is "(1 + 3x + 5x^2)(5 + 3x + 2x^2)" then we have

$$(1 + 3x + 5x^2)(5 + 3x + 2x^2) = (5 + 3x + 2x^2) + (15x + 9x^2 + 6x^3) + (25x^2 + 15x^3 + 10x^4) = 5 + 18x + 36x^2 + 21x^3 + 10x^4$$

And because k = 3 we get 21.

Input

You receive an integer k and several polynomials. k is always a non-negative integer, and so are the coefficients and the exponents in the input polynomials.

k may be larger than the combined degree of all the input polynomials.

The input polynomials can be in any sensible format. A few suggestions come to mind:


A string, like "(1 + 3x + 5x^2)(5 + 3x + 2x^2)"
A list of strings, like ["1 + 3x + 5x^2", "5 + 3x + 2x^2"]
A list of lists of coefficients where index encodes exponent, like [[1, 3, 5], [5, 3, 2]]
A list of lists of (coefficient, exponent) pairs, like [[(1, 0), (3, 1), (5, 2)], [(5, 0), (3, 1), (2, 2)]]


An input format must be sensible AND completely unambiguous over the input space.

Test cases

0, "(1 + 3x + 5x^2)(5 + 3x + 2x^2)" -&gt; 5
1, "(1 + 3x + 5x^2)(5 + 3x + 2x^2)" -&gt; 18
2, "(1 + 3x + 5x^2)(5 + 3x + 2x^2)" -&gt; 36
3, "(1 + 3x + 5x^2)(5 + 3x + 2x^2)" -&gt; 21
4, "(1 + 3x + 5x^2)(5 + 3x + 2x^2)" -&gt; 10
5, "(1 + 3x + 5x^2)(5 + 3x + 2x^2)" -&gt; 0
6, "(1 + 2x^2 + 4x^4)(2x^2 + 4x^4 + 8x^8)(4x^4 + 8x^8 + 16x^16)" -&gt; 8
7, "(1 + 2x^2 + 4x^4)(2x^2 + 4x^4 + 8x^8)(4x^4 + 8x^8 + 16x^16)" -&gt; 0
8, "(1 + 2x^2 + 4x^4)(2x^2 + 4x^4 + 8x^8)(4x^4 + 8x^8 + 16x^16)" -&gt; 32
9, "(1 + 2x^2 + 4x^4)(2x^2 + 4x^4 + 8x^8)(4x^4 + 8x^8 + 16x^16)" -&gt; 0
17, "(1 + 2x^2 + 4x^4)(2x^2 + 4x^4 + 8x^8)(4x^4 + 8x^8 + 16x^16)" -&gt; 0
18, "(1 + 2x^2 + 4x^4)(2x^2 + 4x^4 + 8x^8)(4x^4 + 8x^8 + 16x^16)" -&gt; 160
19, "(1 + 2x^2 + 4x^4)(2x^2 + 4x^4 + 8x^8)(4x^4 + 8x^8 + 16x^16)" -&gt; 0
20, "(1 + 2x^2 + 4x^4)(2x^2 + 4x^4 + 8x^8)(4x^4 + 8x^8 + 16x^16)" -&gt; 384
J, 21 19 18 bytes

{ ::0[:+//.@(*/)/&gt;


Try it online!

-1 byte thanks to FrownyFrog

J has a nice geometric idiom for multiplying polynomials, which we 
represent as lists of coefficients, with explicit zeroes where needed:

+//.@(*/)


Let's see how this works using the example:

1 3 5 +//.@(*/) 5 3 2


First it creates a multiplication table */:

 5  3  2
15  9  6
25 15 10


And @: then it computes the sums along each diagonal +//. using the Oblique /. adverb:



This works because moving down a diagonal is equivalent to decrementing the
power of one x while incrementing the power of another, meaning that the
numbers along a diagonal represent all the components of some a factor x^n
for some n.

The rest of the solution is just mechanics for the problem as stated:

{ ::0[: &lt;polynomial idiom&gt; /&gt;


Since we can have an arbitrary number of polynomials, we represent them as a list of boxes (each box containing one polynomial) and take that as the right arg.  The left arg is the index we want.

Now { ::0 ... is a dyadic hook asking for the index specified by the left arg, after transforming the right arg by everything in ....  And, if you can't find the index, return 0 ::0.

Finally [: &lt;polynomial idiom&gt; /&gt; says to first unbox &gt; the right arg lists, filling any missing coefficients with 0.  Then reduce / that list using the polynomial multiplication idiom.