50021. Polynomial

I'm a slow walker, but I never walk backwards.

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.

Subtasks

  • 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

1
2
3
4
5
6
7
8
9
10
11
12
13
#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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#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

3
3 -3 2 3
2 0 1
3 1 0 1
6
1 0
1 1
1 2
2 0 1
3 0 1
3 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

Discussion