ACM ICPC Asia Manila 2009: Problem D

.
Link to blog post: http://raffysaldana.blogspot.com/2009/10/acm-icpc-asia-manila-2009-problem-d.html

2009 ACM ICPC Asia Manila
October 22 – 23, 2009

Problem D: ‘Composition of Polynomials’
Input file: d.in
Output file: stdout
Execution time limit: 15 seconds


Given two polynomials, p(x) of degree M, and q(x) of degree N, both with integer coefficients, your problem is to write a computer program that prints the coefficients of the composition polynomial f(x) = p(q(x)).

For example, if p(x) = 2x^3 + 5x – 4 and q(x) = 3x^2 – 4x + 1, then f(x) = p(q(x)) = 2(3x^2 – 4x + 1)^3 + 5( 3x^2 – 4x + 1) – 4 = 54x^6 – 216x^5 + 342x^4 – 272x^3 + 129x^2 – 44x + 3

INPUT. Input shall consist of several data sets. Each data set will be given in three lines of input. The first line will give the values of M and N, separated by one or more spaces. The second line will give the coefficients of each term of p(x), separated by one or more spaces, and arranged in increasing powers of x. The third line will give the coefficients of each term of q(x), separated by one or more spaces, and arranged in increasing powers of x. Both M and N will be between 0 and 10, inclusive. Each coefficient will be small, in the range -20 to 20 inclusive, but a small value raised to 10th power is not guaranteed to be a small integer. Input for the next data set will immediately follow that of the previous data set. An input of M = 0 and N = 0 will signify the end of input data.

SAMPLE INPUT
3 2
-4 5 0 2
1 -4 3
2 2
-7 0 2
5 3 2
0 0

OUTPUT.
For each data set, print one line of output of the form:“Data set N: <composition polynomial>”,
where N is the data set number, starting from 1, and <composition polynomial> is the resulting polynomial in decreasing powers of x, with zero terms omitted. If the power of a term is 1, then the power must not be printed. If the coefficient of a term is 1, you may optionally print or not print the coefficient.

OUTPUT FOR SAMPLE INPUT
Data set 1: 54x^6–216x^5+342x^4–272x^3+129x^2–44x+3
Data set 2: 8x^4+24x^3+58x^2+60x+43


(Acknowledgment: This problem was contributed by Dr. Pablo Manalastas, Ateneo de Manila University).
.