/**
 * A class for dense univariate polynoms with integer coefficients
 *
 * @version	$Id: Polynom.java,v 1.1.2.2 2003/10/31 22:16:24 nthiery Exp $
 * @author	Nicolas M. Thiéry <nthiery@users.sourceforge.net>
**/

import java.util.ArrayList;

public class Polynom {

    void assert(boolean condition) {
	if (!condition) {
	    throw new RuntimeException("Assertion failed");
	}
    }

    /**
     * Invariants:
     *  - coefficients is an array of size 2^n for some n
     *  - degree < 2^n
     *  - coefficients[d] = 0 for degree < d < 2^n
     *  - degree=-1 or coefficients[degree] <> 0
     **/
    int degree;
    int [] coefficients;

    /**
     * Creates the zero polynomial
     */
    Polynom() {
	degree = -1;
	coefficients = new int[1];
    }

    /**
     * Creates a polynomial from an array of coefficients of length 2^n
     */
    private Polynom(int[] coeffs) {
	coefficients = coeffs;
	for(degree = coefficients.length - 1;
	    degree >= 0 && coefficients[degree] == 0;
	    degree--);
    }

    /**
     * Translates a string into a polynomial
     */
    Polynom(String s) {
	degree = -1;
	coefficients = new int[1];
	if (s.equals("0")) {
	    return;
	}
	int i=0;
	while(i<s.length()) {
	    int sign=1;
	    if (s.charAt(i)=='+') {
		i++;
	    } else if (s.charAt(i)=='-') {
		sign=-1;
		i++;
	    }
	    int start=i;
	    while(i<s.length() && s.charAt(i)!='x') { i++; };
	    int coeff;
	    if (i==start) {
		coeff=1;
	    } else {
		coeff=Integer.parseInt(s.substring(start,i));
	    }
	    coeff*=sign;
	    if (i+1>=s.length()) {
		throw new RuntimeException("bad format");
	    }
	    i++;
	    if (s.charAt(i)!='^') {
		throw new RuntimeException("bad format: missing ^");
	    }
	    i++;
	    start=i;
	    while(i<s.length() && s.charAt(i)!='+' && s.charAt(i)!='-') {
		i++;
	    };
	    if (i==start) {
		throw new RuntimeException("bad format: missing degree");
	    }
	    int d=Integer.parseInt(s.substring(start,i));
	    setCoeff(d, coeff);
	}
    }

    /**
     * Returns the string representation of p
     **/
    public String toString() {
	if (degree==-1) {
	    return "0";
	}
	String result = "";
	for (int d=0; d<=degree; d++) {
	    if (coefficients[d] != 0) {
		if (coefficients[d]>0 && result.length()>0) {
		    result += "+";
		}
		if (coefficients[d]==1) {
		} else if (coefficients[d]==-1) {
		    result += "-";
		} else {
		    result += coefficients[d];
		}
		result += "x^" + d;
	    }
	}
	return result;
    }
    
    /**
     * Enlarge coefficients if needed to ensure that the index d is valid
     *
     * @param d		a non negative integer
     */
    void resize(int d) {
	if (d < coefficients.length) {
	    return;
	}
	int l = coefficients.length;
	while (d>=l) { l = l*2; };
	int [] newCoefficients = new int[l];
	for (int i=0;i<=degree;i++) {
	    newCoefficients[i]=coefficients[i];
	}
	for (int i=degree+1;i<l;i++) {
	    newCoefficients[i]=0;
	}
	coefficients=newCoefficients;
    }

    /**
     * Clone this polynomial
     *
     * @return		a copy of this polynomial
     */
    public Object clone() {
	Polynom result = new Polynom();
	result.degree = degree;
	result.coefficients = new int[coefficients.length];
	for (int i=0; i<coefficients.length;i++) {
	    result.coefficients[i] = coefficients[i];
	}
	return result;
    }

    /**
     * Returns the coefficient of degree d of P
     *
     * @param d		a non negative integer
     * @return		the coefficient of degree d of P
     */
    public int getCoeff(int d) {
	assert(d>=0);
	if (d > degree) {
	    return 0;
	} else {
	    return coefficients[d];
	}
    }

    /**
     * Set the coefficient of degree d of P to value
     *
     * @param d		a non negative integer
     * @param value	a int
     */
    public void setCoeff(int d, int value) {
	assert(d>=0);
	if (d > degree) {
	    if (value == 0) {
		return;
	    } else {
		resize(d);
		degree=d;
	    };
	};
	coefficients[d] = value;
	if (d == degree && value == 0) {
	    degree --;
	    while (degree >=0 && coefficients[degree] == 0) {
		degree--;
	    }
	};
    }

    /**
     * Return the degree of p
     *
     * @return the degree of p
     */
    public int getDegree() {
	return degree;
    }

    /**
     * Return whether p is the zero polynomial
     *
     * @return whether p is the zero polynomial
     */
    public boolean isZero() {
	return degree == -1;
    }

    /**
     * Return whether p is the zero polynomial
     *
     * @return whether p is the zero polynomial
     */
    public boolean equals(Polynom p) {
	if (degree!=p.degree) {
	    return false;
	}
	for (int d=0;d<=degree;d++) {
	    if (coefficients[d] != p.coefficients[d]) {
		return false;
	    }
	}
	return true;
    }

    /**
     * Evaluates p at a point x
     *
     * This uses the usual Horner scheme of complexity n
     *
     * @param x		a int
     * @return		the evaluation of p at point x
     */
    public int evaluate(int x) {
	int result=0;
	for(int d=degree; d>=0; d--) {
	    result = result * x + coefficients[d];
	}
	return result;
    }

    /**
     * Returns a Polynom which is the sum of this and p
     *
     * Uses plain algorithm with complexity n^2
     *
     * @param p		a polynomial
     * @return		this + p
     */
    public Polynom add(Polynom x) {
	if (degree   ==-1) { return((Polynom)x.clone()); };
	if (x.degree ==-1) { return((Polynom)  clone()); };
	Polynom sum = new Polynom();
	int deg = degree>x.degree ? degree:x.degree;
	sum.resize(deg);
	int i;
	for(i=0; i<=degree && i<=x.degree; i++) {
	    sum.coefficients[i]=coefficients[i] + x.coefficients[i];
	}
	for(; i<=degree; i++) {
	    sum.coefficients[i]=coefficients[i];
	}
	for(; i<=x.degree; i++) {
	    sum.coefficients[i]=x.coefficients[i];
	}
	if (degree == x.degree) {
	    while(deg>=0 && sum.coefficients[deg]==0) {
		deg--;
	    }
	}
	sum.degree=deg;
	return(sum);
    }

    /**
     * negate this polynomial
     *
     * Beware: this is an in-place operation!
     * @return	 'this' after negation
     */
    public Polynom negate() {
	for (int i=0;i<=degree;i++) {
	    coefficients[i]*=-1;
	}
	return this;
    }

    /**
     * Returns a Polynom whose value is (this * p)
     *
     * @param p		a polynomial
     * @return		this * p
     */
    public Polynom multiply(Polynom x) {
	if (degree   ==-1 || x.degree ==-1) { return(new Polynom()); };
	Polynom prod = new Polynom();
	int deg = degree+x.degree;
	prod.resize(deg);
	for(int d=0; d<=deg; d++) {
	    int coeff=0;
	    int i=0;
	    if (d>x.degree) {
		i=d-x.degree;
	    };
	    for(;i<=d && i<=degree;i++) {
		coeff += coefficients[i] * x.coefficients[d-i];
	    }
	    prod.coefficients[d] = coeff;
	}
	prod.degree=deg;
	return prod;
    }

    /**
     * Creates the polynom
     * p = p_0 + x^d p_1 + x^2d p_2 + ...
     *
     * @param polyList  a list of 2^n polynomials [p_0,p_1,\dots,] of length 2d
     * @return		the list [p_0,p_1,\dots,]
     */
    private Polynom(Polynom[] polyList, int d) {
	coefficients = new int[(polyList.length+1)*d];
	for (int j=0; j < 2*d && j <= polyList[0].degree; j++) {
	    coefficients[j]=polyList[0].coefficients[j];
	}
	for (int i=1; i<polyList.length;i++) {
	    int k = d*i;
	    for (int j=0; j < 2*d && j <= polyList[i].degree; j++, k++) {
		coefficients[k]+=polyList[i].coefficients[j];
	    }
	}
	for(degree = coefficients.length-1;
	    degree>=0 && coefficients[degree]==0;
	    degree--);
	/*	for(int i=0;i<polyList.length;i++) size+=polyList[i].coefficients.length;
	coefficients = new int[size];
	int k=0;
	for (int i=0; i<polyList.length;i++) {
	    for (int j=0;polyList[i].length;j++,k++) {
		coefficients[k]=polyList[i].coefficients[j];
	    }
	}
	for(degree = coefficients.length-1;
	    degree>=0 && coefficients[degree]==0;
	    degree--);
	*/
    }

    /**
     * splits a polynomial p in a list of polynoms of degree < d such that
     * p = p_0 + x^d p_1 + x^2d p_2 + ...
     *
     * @param d		a power of 2 which divides this.length
     * @return		the list [p_0,p_1,\dots,]
     */
    private Polynom[] split(int d) {
	Polynom [] result = new Polynom[coefficients.length/d];
	int k=0;
	for (int i=0; i<coefficients.length/d;i++) {
	    int[] coeffs = new int[d];
	    for (int j=0;j<d;j++,k++) {
		coeffs[j]=coefficients[k];
	    }
	    result[i] = new Polynom(coeffs);
	}
	return result;
    }

    /**
     * Returns a Polynom whose value is (this * p)
     *
     * Uses Karatsuba algorithm with complexity n^{3/2}
     *
     * @param p		a polynomial
     * @return		this * p
     */
    public Polynom multiplyKaratsuba(Polynom x) {
	// Threshold under which standard multiplication is
	// used instead of Karatsuba
	int threshold = 4;

	if (coefficients.length > x.coefficients.length) {
	    return x.multiplyKaratsuba(this);
	}
	if (coefficients.length < x.coefficients.length) {
	    //System.out.println("this: "+this+" * x: "+x);
	    int ratio = x.coefficients.length / coefficients.length;
	    Polynom[] l = x.split(coefficients.length);
	    for (int i=0; i<l.length;i++) {
		//System.out.println("l["+i+"]: "+l[i]);
		l[i] = multiplyKaratsuba(l[i]);
		//System.out.println("this*l["+i+"]: "+l[i]);
	    }
	    return new Polynom(l, coefficients.length);
	} if (coefficients.length < threshold) {
	    return multiply(x);
	}
	Polynom[] l = new Polynom[3];
	Polynom[] a =   split(coefficients.length/2);
	Polynom[] b = x.split(coefficients.length/2);
	// a0*b0
	l[0]=a[0].multiplyKaratsuba(b[0]);
	// a1*b1
	l[2]=a[1].multiplyKaratsuba(b[1]);
	// (a0+a1) * (b0+b1) - a0*b0 - a1*b1 = a0*b1 + a1*b0
	l[1]=(a[0].add(a[1])).multiply(b[0].add(b[1]))
	    .add(l[0].add(l[2]).negate());
	//System.out.println(l[0] + " +x^d*"+l[1]+" +x^2d*"+l[2]);
	return new Polynom(l, coefficients.length/2);
    }

    /**
     * Returns a Polynom whose value is (this * p)
     *
     * Uses FFT algorithm with complexity n log n
     *
     * @param p		a polynomial
     * @return		this * p
     */
    public Polynom multiplyFFT(Polynom x) {
	return new Polynom();
    }
}