# 50021. Polynomial

## Problem Description

Implement a polynomial. A polynomial can be represent by its coefficients. Please implement the following functions. We assume that there will be at most 4096 terms in a polynomial. That is, the maximum power of a term is no more than 4095.

• void init(Polynomial *poly, int coefficient[], int n);
Initialize a polynomial according to the coefficient[n-1] ... to coefficient[0], where coefficient[i] is the coefficient of $x$ to the power of $i$. It is guaranteed that the leading coefficient[n-1] is not 0.
• Polynomial add(Polynomial *poly1, Polynomial *poly2);
Add two polynomials and return the sum.
• Polynomial multiply(Polynomial *poly1, Polynomial *poly2);
Multiply two polynomials and return the product.
• void print(Polynomial *poly);
Print a polynomial, e.g., +3x^4+1x^2-2x-3. For simplicity we print all coefficient with its sign. We also assume that the polynomial will never be 0.
• Do not print a term if the coefficient is 0, like the power of 3 above.
• Do not print the power if it is 1 or 0, like the -2x and -3 above.

• 25pt. Implement init and print.
• 30pt. Implement init, add, and print.
• 35pt. Implement init, add, multiply, and print.
• 10pt. Implement init, add, multiply, and print efficiently.

## Hints

In order to implement multiplication efficiently, you cannot treat the polynomial as if it has all 4096 terms. Instead you need to remember the number of terms in a polynomial, and process only these terms. You can use "%+d" to force printf to print an integer with a '+' or a '-', depending on it is positive or negative.

## polynomial.h

12345678910111213#ifndef _POLYNOMIAL_H#define _POLYNOMIAL_H /*    define structure polynomial*/ void init(Polynomial *poly, int coefficient[], int n);Polynomial add(Polynomial *poly1, Polynomial *poly2); Polynomial multiply(Polynomial *poly1, Polynomial *poly2);void print(Polynomial *poly); #endif


## main.c

1234567891011121314151617181920212223242526272829303132333435363738394041#include "polynomial.h" #include <stdio.h>#include <stdlib.h>#include <string.h>#include <assert.h> void test_specall() {    int n, m;    int cmds, cmd, pid, pid2;    int v[4096];    scanf("%d", &n);    Polynomial *p = (Polynomial*) malloc(sizeof(Polynomial)*n);    for (int i = 0; i < n; i++) {        scanf("%d", &m);        for (int j = 0; j < m; j++)            scanf("%d", &v[j]);        init(&p[i], v, m);    }    scanf("%d", &cmds);    for (int i = 0; i < cmds; i++) {        scanf("%d %d", &cmd, &pid);        if (cmd == 1) {            print(&p[pid]);        } else if (cmd == 2) {            scanf("%d", &pid2);            Polynomial ret = add(&p[pid], &p[pid2]);            print(&ret);        } else if (cmd == 3) {            scanf("%d", &pid2);            Polynomial ret = multiply(&p[pid], &p[pid2]);            print(&ret);        } else {            assert(0);        }    }}int main() {    test_specall();    return 0;}


## Sample Input

33 -3 2 32 0 13 1 0 161 01 11 22 0 13 0 13 0 2


## Sample Output

+3x^2+2x-3+1x+1x^2+1+3x^2+3x-3+3x^3+2x^2-3x+3x^4+2x^3+2x-3