#include <stdio.h>
#include <stdlib.h>

#define NVAR 6

typedef struct {
   int nterm;
   int (*term)[1+NVAR];
} mvpoly;

void polyprint ( mvpoly f )
{
   int i, k;

   for (i=0; i<f.nterm; ++i) if (f.term[i][0]) {
      if ((i)&&(f.term[i][0]>=0)) printf("+");
      if (f.term[i][0] != 1) printf("%d", f.term[i][0]);
      for (k=1; k<=NVAR; ++k) {
         if (f.term[i][k]) printf("%c",'a'+(char)(k-1));
         if (f.term[i][k]>1) printf("^%d", f.term[i][k]);
      }
   }
}

mvpoly setpoly ()
{
   mvpoly h;
   int i, k;

   h.nterm = NVAR;
   h.term = (int (*)[1+NVAR])malloc(NVAR * sizeof(int[1+NVAR]));
   for (i=0; i<NVAR; ++i) {
      h.term[i][0] = 1;       /* Set the coefficient to 1 */
      for (k=1; k<=NVAR; ++k) /* Only the kth variable has power 1 */
         h.term[i][k] = (k == (i+1)) ? 1 : 0;
   }
   return h;
}

mvpoly polyprod ( mvpoly f, mvpoly g )
{
   int i, j, k, l;
   mvpoly h;        /* The output is computed here */
   int deg[1+NVAR]; /* Temporary storage of degrees of product monomials */
   int found;       /* A flag to locate monomials already added to h */

   /* Allocate maximum possible memory for the product */
   h.term = (int (*)[1+NVAR])malloc(f.nterm * g.nterm * sizeof(int[1+NVAR]));

   h.nterm = 0;
   for (i=0; i<f.nterm; ++i) {
      for (j=0; j<g.nterm; ++j) {
         /* First compute the product monomial */
         for (k=1; k<=NVAR; ++k) deg[k] = f.term[i][k] + g.term[j][k];

         /* Check whether the product monomial already exists */
         found = 0;
         for (l=0; l<h.nterm; ++l) {
            found = 1;
            for (k=1; k<=NVAR; ++k) {
               if (h.term[l][k] != deg[k]) {
                  found = 0; break;
               }
            }
            if (found) break;
         }

         if (found) { /* Adjust the coefficient */
            h.term[l][0] += f.term[i][0] * g.term[j][0];
         } else {     /* Create a new term */
            h.term[h.nterm][0] = f.term[i][0] * g.term[j][0];
            for (k=1; k<=NVAR; ++k) h.term[h.nterm][k] = deg[k];
            ++h.nterm;
         }
      }
   }

   /* This function does not remove zero terms produced as in the example
      (a+b)(a-b) = a^2-ab+ab-b^2. A good product function sould take care
      of this. However, the assignment does not require this, since no
      coefficient generated as above can be zero. */

   /* Adjust allocated memory to an amount just sufficient to store only the
      non-zero terms */
   h.term = (int (*)[1+NVAR])realloc(h.term, h.nterm * sizeof(int[1+NVAR]));

   return h;
}

int main ()
{
   mvpoly f, g, h;
   int i;

   /* Initialize f and g by making two separate calls of setpoly() */
   f = setpoly();
   g = setpoly();

   printf("("); polyprint(f); printf(")^1 = "); polyprint(g); printf("\n\n");

   for (i=2; i<=NVAR; ++i) {
      h = polyprod(g,f);  /* Store the product in h */
      free(g.term);       /* Free memory currently allocated to g */
      g = h;              /* Copy h to g */
      printf("("); polyprint(f); printf(")^%d = ", i); polyprint(g); printf("\n\n");
   }

   /* Free remaining memory */
   free(f.term);
   free(g.term);

   exit(0);
}