import java.util.Arrays;

/**
* Robert Sedgewick Algorithms in C++<br>
* Chapter 36 Arithmetic<br>
* Problem2<br>
* 非ゼロ要素に対応する節点からなるリンクによるリストを用いて疎な多項式の積を計算するプログラムを書け。
*/
public class Chapter36ArithmeticProblem2 {
public static void main(String[] args) {
Chapter36ArithmeticProblem2 o = new Chapter36ArithmeticProblem2();
o.run();
}

private class Node {
int c;
int j;
Node next;
}

private void run() {
Node t = new Node();
Node i = insert(t, 1, 0);
i = insert(i, 1, 10);
i = insert(i, -1, 100);

Node mult = t;
for (int k = 0; k < 10; k++) {
mult = mult(t, mult);

mult = simple(mult);

for (Node l = mult.next; l != null; l = l.next) {
System.out.format(" + %d*x^%d", l.c, l.j);
}
System.out.format("\n");
}
}

private Node mult(Node t, Node t2) {
Node m = new Node();
Node n = m;
for (Node i = t.next; i != null; i = i.next) {
for (Node j = t2.next; j != null; j = j.next) {
n = insert(n, i.c * j.c, i.j + j.j);
}
}
return m;
}

private Node simple(Node t) {
Node s = new Node();
Node n = s;
for (Node i = t.next; i != null; i = i.next) {
boolean exists = false;
for (Node j = s.next; j != null; j = j.next) {
if (j.j == i.j) {
j.c += i.c;
exists = true;
break;
}
}
if (!exists) {
n = insert(n, i.c, i.j);
}
}
for (Node j = s; j != null; j = j.next) {
if (j.next != null && j.next.c == 0) {
j.next = j.next.next;
}
}
for (;;) {
boolean exists = false;
for (Node j = s; j != null; j = j.next) {
if (j.next != null && j.next.next != null && j.next.j > j.next.next.j) {
Node tmp = j.next;
j.next = j.next.next;
Node tmp2 = j.next.next;
j.next.next = tmp;
j.next.next.next = tmp2;
exists = true;
}
}
if (!exists) {
break;
}
}
return s;
}

private Node insert(Node t, int c, int j) {
t.next = new Node();
t.next.c = c;
t.next.j = j;
return t.next;
}

private static final boolean DEBUG = true;

private static final void debug(Object... o) {
if (DEBUG)
System.err.println(Arrays.deepToString(o));
}

private static final void message(Object... o) {
System.err.println(Arrays.deepToString(o));
}

}