public class PolyNomial
    {
        public int[] _coefficients;
        public PolyNomial()
        {
        }
        public PolyNomial(int degree)
        {
            _coefficients = new int[degree];
        }
        public PolyNomial(params int[] coeffs)
        {
            _coefficients = new int[coeffs.Length];
            var i = 0;
            foreach (var v in coeffs)
                _coefficients[i++] = v;
        }
        public PolyNomial(PolyNomial p)
        {
            _coefficients = new int[p.Degree];
            for (var i = 0; i < p.Degree; i++)
                _coefficients[i] = p._coefficients[i];
        }
        public PolyNomial(string binary)
        {
            _coefficients = new int[binary.Length];
            var coeffs = new int[binary.Length];
            var rb     = binary.ToArray();
            var n      = 0;
            for (var p = 0; p < rb.Count(); p++)
            {
                if (rb[p] == '1')
                    coeffs[p] = 1;
                if (rb[p] == '0')
                    coeffs[p] = 0;
            }
            var i = 0;
            foreach (var v in coeffs)
                _coefficients[i++] = v;
        }
        public PolyNomial(BigInteger bi)
        {
            var binary = bi.ToBinaryString();
            _coefficients = new int[binary.Length];
            var coeffs = new int[binary.Length];
            var rb     = binary.ToArray();
            var n      = 0;
            for (var p = 0; p < rb.Count(); p++)
            {
                if (rb[p] == '1')
                    coeffs[p] = 1;
                if (rb[p] == '0')
                    coeffs[p] = 0;
            }
            var i = 0;
            foreach (var v in coeffs)
                _coefficients[i++] = v;
        }
        public int this[int n] => n < _coefficients.Length ? _coefficients[n] : 0;
        public int Degree => _coefficients.Length;
        private static PolyNomial AddSubXor(PolyNomial poly1, PolyNomial poly2)
        {
            var n      = Math.Min(poly1.Degree, poly2.Degree);
            var coeffs = new int[n];
            for (var i = 0; i < n; i++)
                coeffs[i] = poly1[i] ^ poly2[i];
            return new PolyNomial(coeffs);
        }
        public PolyNomial BigIntegerToPoly(BigInteger val)
        {
            var mc = 0;
            for (mc = 0; mc < 10240; ++mc)
                if ((BigInteger) 1 << mc > val)
                    break;
            var coeffs = new int[mc];
            for (var i = 0; i < mc; i++)
            {
                var mask = (BigInteger) 1 << i;
                coeffs[i] = (int) ((val & mask) >> i);
            }
            coeffs = Reverse(coeffs);
            return new PolyNomial(coeffs);
        }
        public static PolyNomial Builder(PolyNomial p, int index, int dig)
        {
            if (p._coefficients == null)
                p._coefficients = new int[1];
            if (index > p.Degree + 1)
                throw new Exception("Builder can only be used to add/modify one digit at a time.");
            var add = p.Degree;
            if (index > p.Degree - 1)
                add = p.Degree + 1;
            var np = new PolyNomial(add);
            for (var i = 0; i < p.Degree; i++)
                np._coefficients[i] = p._coefficients[i];
            np._coefficients[index] = dig;
            return np;
        }
        public void Clear(PolyNomial p)
        {
            for (var i = 0; i < p.Degree; ++i)
                p._coefficients[i] = 0;
        }
        public static PolyNomial Clone(PolyNomial p, int newdegree = 0)
        {
            var size = p.Degree;
            if (newdegree != 0)
                size = newdegree;
            var np = new PolyNomial(size);
            for (var i = 0; i < size; i++)
                np._coefficients[i] = p._coefficients[i];
            return np;
        }
        public static PolyNomial Concat(PolyNomial p, int dig)
        {
            var np = new PolyNomial(p.Degree + 1);
            for (var i = 0; i < p.Degree; i++)
                np._coefficients[i] = p._coefficients[i];
            np._coefficients[np.Degree - 1] = dig;
            return np;
        }
        public static PolyNomial CopyFromMsb(PolyNomial p, int digits)
        {
            var coeffs = new int[digits];
            for (var i = 0; i < digits; ++i)
                coeffs[i] = p._coefficients[i];
            return new PolyNomial(coeffs);
        }
        public bool Equals(PolyNomial poly1, PolyNomial poly2)
        {
            if (poly1 == null)
                return false;
            if (poly2 == null)
                return false;
            if (poly1.Degree != poly2.Degree)
                return false;
            for (var i = 0; i < poly1.Degree; i++)
                if (poly1._coefficients[i] != poly2._coefficients[i])
                    return false;
            return true;
        }
        public int GetParity(PolyNomial p)
        {
            var parity = p._coefficients[0];
            for (var i = 1; i < p.Degree; i++)
                parity ^= p._coefficients[i];
            return parity;
        }
        public PolyNomial Invert(PolyNomial p)
        {
            var T = Clone(p);
            for (var i = T.Degree; i >= 0; i--)
                switch (T._coefficients[i])
                {
                    case 0:
                        T._coefficients[i] = 1;
                        continue;
                    case 1:
                        T._coefficients[i] = 0;
                        break;
                }
            return T;
        }
        private static PolyNomial LeftShift(PolyNomial p, int n)
        {
            var T = new PolyNomial(p.Degree + n);
            for (var i = 0; i < p.Degree; i++)
                T._coefficients[i] = p._coefficients[i];
            T = LeftTrim(T, p.Degree);
            return T;
        }
        public static PolyNomial LeftTrim(PolyNomial p, int minSize)
        {
            var loc = 0;

            for (var i = 0; i < p.Degree; ++i)
                if (p._coefficients[i] == 1)
                {
                    loc = i;
                    break;
                }
            if (p.Degree - loc > minSize)
            {
            }
            var T = new PolyNomial(minSize);
            if (loc == p.Degree - 1)
            {
                T._coefficients[0] = 1;
                return T;
            }
            var ptr = minSize - 1;
            for (var i = p.Degree - 1; i >= 0 && ptr >= 0; --i, --ptr)
                T._coefficients[ptr] = p._coefficients[i];
            return T;
        }
        public static int MsbDegree(PolyNomial p)
        {
            var loc = 0;
            for (var i = 0; i < p.Degree; ++i)
                if (p._coefficients[i] == 1)
                {
                    loc = i;
                    break;
                }
            return p.Degree - loc;
        }
        public static PolyNomial operator +(PolyNomial poly1, PolyNomial poly2)
        {
            return AddSubXor(poly1, poly2);
        }
        public static PolyNomial[] operator /(PolyNomial dividend, PolyNomial divisor)
        {
            var Quotient       = new PolyNomial();
            var Remainder      = new PolyNomial();
            var Divisormsbdeg  = MsbDegree(divisor);
            var Dividendmsbdeg = MsbDegree(dividend);
            var q              = Divisormsbdeg;
            var answer         = new PolyNomial[2];
            if (Dividendmsbdeg < Divisormsbdeg)
            {
                answer[0] = Quotient;
                answer[1] = divisor;
                return answer;
            }
            if (Dividendmsbdeg >= Divisormsbdeg)
            {
                Quotient  = Builder(Quotient, 0, 1);
                Remainder = CopyFromMsb(dividend, divisor.Degree) - divisor;
                Remainder = LeftShift(Remainder, 1);
                Remainder = Builder(Remainder, divisor.Degree - 1, dividend._coefficients[q++]);
            }
            else
            {
                Quotient = Builder(Quotient, 0, 0);
            }
            var qp = 1;
            do
            {
                var Remaindermsbdeg = MsbDegree(Remainder);
                if (Remaindermsbdeg >= Divisormsbdeg)
                {
                    Quotient  = Builder(Quotient, qp++, 1);
                    Remainder = Remainder - divisor;
                    Remainder = LeftShift(Remainder, 1);
                    Remainder = Builder(Remainder, divisor.Degree - 1, dividend._coefficients[q++]);
                }
                else
                {
                    Quotient  = Builder(Quotient, qp++, 0);
                    Remainder = Remainder - new PolyNomial(divisor.Degree);
                    Remainder = LeftShift(Remainder, 1);
                    if (q < Dividendmsbdeg)
                        Remainder = Builder(Remainder, divisor.Degree - 1, dividend._coefficients[q++]);
                }
            } while (q < Dividendmsbdeg);
            if (MsbDegree(Remainder) >= Divisormsbdeg)
            {
                Quotient  = Concat(Quotient, 1);
                Remainder = Remainder - divisor;
                Remainder = TrimNonMsb(Remainder);
            }
            answer[0] = Quotient;
            answer[1] = Remainder;
            return answer;
        }
        public static PolyNomial operator ^(PolyNomial poly1, PolyNomial poly2)
        {
            return AddSubXor(poly1, poly2);
        }
        public static PolyNomial operator <<(PolyNomial p, int shift)
        {
            return LeftShift(p, shift);
        }

        public static PolyNomial operator *(PolyNomial poly1, PolyNomial poly2)
        {
            var n      = Math.Min(poly1.Degree, poly2.Degree);
            var coeffs = new int[n];
            for (var i = 0; i < n; i++)
                if (poly1[i] == 1 && poly2[i] == 1)
                    coeffs[i] = 1;
                else
                    coeffs[i] = 0;
            return new PolyNomial(coeffs);
        }
        public static PolyNomial operator -(PolyNomial poly1, PolyNomial poly2)
        {
            return AddSubXor(poly1, poly2);
        }
        private static int[] Reverse(int[] a)
        {
            var n = 0;
            var T = new int[a.Length];
            for (var i = a.Length - 1; i >= 0; i--)
                T[n++] = a[i];
            return T;
        }
        public BigInteger ToBigInteger(PolyNomial p)
        {
            BigInteger Dec = 0;
            var        T   = Clone(p);
            T._coefficients = Reverse(T._coefficients);
            for (var i = T.Degree - 1; i >= 0; --i)
                if (T._coefficients[i] == 1)
                    Dec += (BigInteger) 1 << i;
            return Dec;
        }
        public string ToBinaryString(PolyNomial p)
        {
            var sb = new StringBuilder();
            var T  = Clone(p);
            for (var i = 0; i < T.Degree; i++)
                sb.Append(T._coefficients[i] == 1 ? "1" : "0");
            return sb.ToString();
        }
        public override string ToString()
        {
            var T = Clone(this);
            T._coefficients = Reverse(_coefficients);
            switch (T.Degree)
            {
                case 0:
                    return "";
                case 1:
                    return $"{ToBinaryString(this)}," + "x + " + T._coefficients[0];
            }
            var s = "";
            for (var i = T.Degree - 1; i >= 0; i--)
            {
                if (T._coefficients[i] == 0)
                    continue;
                if (T._coefficients[i] > 0)
                {
                    if (s != "")
                        s += " + " + T._coefficients[i];
                    else
                        s += T._coefficients[i];
                }
                if (i == 1)
                    s += "x";
                else
                    if (i > 1)
                        s += "x^" + i;
            }
            var rs = s;
            try
            {
                if (T._coefficients.Length <= 64)
                    rs = $"{ToBinaryString(this)}," + s;
                else
                    rs = $"{ToBinaryString(this)}," + s;
            }
            catch (Exception)
            {
                rs = s;
            }
            return rs;
        }
        public ulong ToUInt64(PolyNomial p)
        {
            if (p.Degree > 64)
                throw new Exception("Polynomial coefficients array length exceeds 64 bit math.");
            ulong Dec = 0;
            var   T   = Clone(p);
            T._coefficients = Reverse(T._coefficients);
            for (var i = T.Degree - 1; i >= 0; --i)
                if (T._coefficients[i] == 1)
                    Dec += (ulong) (1 << i);
            return Dec;
        }
        public static PolyNomial TrimNonMsb(PolyNomial p)
        {
            var loc = 0;

            for (var i = 0; i < p.Degree; ++i)
                if (p._coefficients[i] == 1)
                {
                    loc = i;
                    break;
                }
            var T = new PolyNomial(p.Degree - loc);
            if (loc == p.Degree - 1)
            {
                T._coefficients[0] = 1;
                return T;
            }

            for (var i = loc; i < p.Degree; ++i)
                T._coefficients[i - loc] = p._coefficients[i];
            return T;
        }
        public PolyNomial UInt64ToPoly(ulong ul)
        {
            var mc = 0;
            for (mc = 0; mc < 64; ++mc)
                if ((ulong) (1 << mc) > ul)
                    break;
            var coeffs = new int[mc];
            for (var i = 0; i < mc; i++)
            {
                var mask = (ulong) (1 << i);
                coeffs[i] = (int) ((ul & mask) >> i);
            }
            coeffs = Reverse(coeffs);
            return new PolyNomial(coeffs);
        }
    }