local m={}local B=function(m)local B={}for m,D in ipairs(m)do B[m]=D end return B end local D={}local X=function(m)local X=setmetatable(B(m),D)rawset(X,"\115\121\109\098\111\108","\120")return X end local h=function(m,B)m.symbol=B end local Z=function(m,B,D)local h={}for m=1,m,1 do h[m]=0 end for X=1,#D,1 do h[m+X]=B*D[X]end return X(h)end local n=function(m,B)if#m==1 then return m[1]end local D=m[#m-1]+B*m[#m]for X=#m-1,2,-1 do D=m[X-1]+B*D end return D end local V=function(m)local B={}for D=1,#m-1,1 do B[D]=D*m[D+1]end return X(B)end local Y=function(m,B)local D={B}for B=2,#m+1,1 do D[B]=m[B-1]/(B-1)end return X(D)end D.__add=function(m,B)local D={}local h=math.min(#m,#B)local Z=math.max(#m,#B)for X=1,h,1 do D[X]=m[X]+B[X]end if h==Z then return X(D)elseif#m>#B then for B=h+1,Z,1 do D[B]=m[B]end else for m=h+1,Z,1 do D[m]=B[m]end end return X(D)end D.__sub=function(m,B)local D={}local h=math.min(#m,#B)local Z=math.max(#m,#B)for X=1,h,1 do D[X]=m[X]-B[X]end if h==Z then return X(D)elseif#m>#B then for B=h+1,Z,1 do D[B]=m[B]end else for m=h+1,Z,1 do D[m]=-B[m]end end return X(D)end D.__unm=function(m)local B={}for D=1,#m,1 do B[D]=-m[D]end return X(B)end D.__mul=function(m,B)local D=X({})for X=1,#m,1 do D=D+Z(X-1,m[X],B)end return D end D.__tostring=function(m)local B=""local D=true local X=true for B=1,#m,1 do X=X and m[B]==0 end if#m==0 or X then return"\048"elseif#m==1 then return tostring(m[1])end for X=1,#m,1 do if m[X]~=0 and D then if m[X]~=1 or X==1 then B=B..tostring(m[X])end if X==2 then B=B..m.symbol elseif X>1 then B=B..(m.symbol..("\094"..tostring(X-1)))end D=false elseif m[X]~=0 and X>1 then if m[X]~=1 or X==1 then B=B..(" \043 "..tostring(m[X]))else B=B.." \043 "end if X==2 then B=B..m.symbol elseif X>1 then B=B..(m.symbol..("\094"..tostring(X-1)))end end end return B end m.polynomial={}m.polynomial.new=function(m)return X(m)end m.polynomial.eval=function(m,B)return n(m,B)end m.polynomial.derivative=function(m)return V(m)end m.polynomial.integral=function(m,B)return Y(m,B)end m.polynomial.setSymbol=function(m,B)h(m,B)end m.polynomial.constant=function(m)return X({m})end local W={}local L=function(m)local B=setmetatable({},W)rawset(B,"\114\117\108\101",m)return B end local p=function(m,B)local D={}local h=m.rule for m=1,B,1 do D[m]=h(m)end return X(D)end local R=function(m)local B=m.rule if B(1)==0 then error("\078\111\110-\105\110\101\118\114\116\105\098\108\101 \102\111\114\109\097\108 \112\111\119\101\114 \115\101\114\105\101\115\033",2)end local D D=function(m)if m==1 then return 1/B(1)else local X=0 for h=2,m,1 do X=X-B(h)*D((m-h)+1)end return X/B(1)end end return L(D)end local q=function(m)local B=m.rule local D=function(m)return m*B(m+1)end return L(D)end local j=function(m,B)local D=m.rule local X=function(m)if m==1 then return B else return D(m-1)/(m-1)end end return L(X)end W.__add=function(m,B)local D=function(D)return m.rule(D)+B.rule(D)end return L(D)end W.__sub=function(m,B)local D=function(D)return m.rule(D)-B.rule(D)end return L(D)end W.__mul=function(m,B)local D=function(D)local X=0 local h=m.rule local Z=B.rule for m=1,D,1 do X=X+h(m)*Z((D-m)+1)end return X end return L(D)end W.__index=function(m,B)return m.rule(B)end m.formalSeries={}m.formalSeries.new=function(m)return L(m)end m.formalSeries.partialSum=function(m,B)return p(m,B)end m.formalSeries.inverse=function(m)return R(m)end m.formalSeries.derivative=function(m)return q(m)end m.formalSeries.integral=function(m,B)return j(m,B)end return m
local polynomialAlgebra = {}

local shallowCopyTable = function (table)
    local result = {}

    for key, value in ipairs(table) do
        result[key] = value
    end

    return result
end

local _polynomial = {}

local _polynomialFromArray = function (table)
    local polynomial = setmetatable(shallowCopyTable(table), _polynomial)

    rawset(polynomial, "symbol", "x")

    return polynomial
end

local _polynomialSetSymbol = function (polynomial, symbol)
    polynomial["symbol"] = symbol
end

local _polynomialShiftAndScale = function (s, c, polynomial)
    local result = {}

    for i = 1, s do
        result[i] = 0
    end

    for i = 1, #polynomial do
        result[s + i] = c * polynomial[i]
    end

    return _polynomialFromArray(result)
end

local _polynomialEvaluate = function (polynomial, c)
    if #polynomial == 1 then
        return polynomial[1]
    end

    local eval = polynomial[#polynomial - 1] + c * polynomial[#polynomial]

    for i = #polynomial - 1, 2, -1 do
        eval = polynomial[i - 1] + c * eval
    end

    return eval
end

local _polynomialFormalDerivative = function (polynomial)
    local result = {}

    for i = 1, #polynomial - 1 do
        result[i] = i * polynomial[i + 1]
    end

    return _polynomialFromArray(result)
end

local _polynomialFormalAntiderivative = function (polynomial, c)
    local result = {c}

    for i = 2, #polynomial + 1 do
        result[i] = polynomial[i - 1] / (i - 1)
    end

    return _polynomialFromArray(result)
end

_polynomial.__add = function(left, right)
    local result = {}

    local minLength = math.min(#left, #right)
    local maxLength = math.max(#left, #right)

    for i = 1, minLength do
        result[i] = left[i] + right[i]
    end

    if minLength == maxLength then
        return _polynomialFromArray(result)
    elseif #left > #right then
        for i = minLength + 1, maxLength do
            result[i] = left[i]
        end
    else
        for i = minLength + 1, maxLength do
            result[i] = right[i]
        end
    end

    return _polynomialFromArray(result)
end

_polynomial.__sub = function(left, right)
    local result = {}

    local minLength = math.min(#left, #right)
    local maxLength = math.max(#left, #right)

    for i = 1, minLength do
        result[i] = left[i] - right[i]
    end

    if minLength == maxLength then
        return _polynomialFromArray(result)
    elseif #left > #right then
        for i = minLength + 1, maxLength do
            result[i] = left[i]
        end
    else
        for i = minLength + 1, maxLength do
            result[i] = -right[i]
        end
    end

    return _polynomialFromArray(result)
end

_polynomial.__unm = function (polynomial)
    local result = {}

    for i = 1, #polynomial do
        result[i] = -polynomial[i]
    end

    return _polynomialFromArray(result)
end

_polynomial.__mul = function(left, right)
    local result = _polynomialFromArray({})

    for i = 1, #left do
        result = result + _polynomialShiftAndScale(i - 1, left[i], right)
    end

    return result
end

_polynomial.__tostring = function (polynomial)
    local result = ""

    local check = true
    local zeroCheck = true

    for i = 1, #polynomial do
        zeroCheck = zeroCheck and polynomial[i] == 0
    end

    if #polynomial == 0 or zeroCheck then
        return "0"
    elseif #polynomial == 1 then
        return tostring(polynomial[1])
    end

    for i = 1, #polynomial do
        if polynomial[i] ~= 0 and check then
            if polynomial[i] ~= 1 or i == 1 then
                result = result .. tostring(polynomial[i])
            end
            if i == 2 then
                result = result .. polynomial["symbol"]
            elseif i > 1 then
                result = result .. polynomial["symbol"] .. "^" .. tostring(i - 1)
            end
            check = false
        elseif polynomial[i] ~= 0 and i > 1 then
            if polynomial[i] ~= 1 or i == 1 then
                result = result .. " + " .. tostring(polynomial[i])
            else
                result = result .. " + "
            end
            if i == 2 then
                result = result .. polynomial["symbol"]
            elseif i > 1 then
                result = result .. polynomial["symbol"] .. "^" .. tostring(i - 1)
            end
        end
    end

    return result
end

polynomialAlgebra.polynomial = {}

polynomialAlgebra.polynomial.new = function (array)
    return _polynomialFromArray(array)
end

polynomialAlgebra.polynomial.eval = function (polynomial, c)
    return _polynomialEvaluate(polynomial, c)
end

polynomialAlgebra.polynomial.derivative = function (polynomial)
    return _polynomialFormalDerivative(polynomial)
end

polynomialAlgebra.polynomial.integral = function (polynomial, c)
    return _polynomialFormalAntiderivative(polynomial, c)
end

polynomialAlgebra.polynomial.setSymbol = function (polynomial, symbol)
    _polynomialSetSymbol(polynomial, symbol)
end

polynomialAlgebra.polynomial.constant = function (r)
    return _polynomialFromArray({r})
end

local _formalSeries = {}

local _formalSeriesFromRule = function (rule)
    local formalSeries = setmetatable({}, _formalSeries)

    rawset(formalSeries, "rule", rule)

    return formalSeries
end

local _polynomialFromFormalSeries = function (formalSeries, n)
    local result = {}
    local rule = formalSeries["rule"]

    for i = 1, n do
        result[i] = rule(i)
    end

    return _polynomialFromArray(result)
end

local _formalSeriesInverse = function (formalSeries)
    local seriesRule = formalSeries["rule"]
    
    if seriesRule(1) == 0 then
        error("Non-inevrtible formal power series!", 2)
    end

    local rule

    rule = function (n)
        if n == 1 then
            return 1/seriesRule(1)
        else
            local sum = 0
            for i = 2, n do
                sum = sum - seriesRule(i) * rule(n - i + 1)
            end
            return sum/seriesRule(1)
        end
    end

    return _formalSeriesFromRule(rule)
end

local _formalSeriesDerivative = function (formalSeries)
    local seriesRule = formalSeries["rule"]

    local rule = function (n)
        return n * seriesRule(n + 1)
    end

    return _formalSeriesFromRule(rule)
end

local _formalSeriesAntiderivative = function (formalSeries, c)
    local seriesRule = formalSeries["rule"]

    local rule = function (n)
        if n == 1 then
            return c
        else
            return seriesRule(n - 1) / (n - 1)
        end
    end

    return _formalSeriesFromRule(rule)
end

_formalSeries.__add = function (left, right)
    local rule = function (n)
        return left["rule"](n) + right["rule"](n)
    end

    return _formalSeriesFromRule(rule)
end

_formalSeries.__sub = function (left, right)
    local rule = function (n)
        return left["rule"](n) - right["rule"](n)
    end

    return _formalSeriesFromRule(rule)
end

_formalSeries.__mul = function (left, right)
    local rule = function (n)
        local sum = 0

        local leftRule = left["rule"]
        local rightRule = right["rule"]

        for i = 1, n do
            sum = sum + leftRule(i) * rightRule(n - i + 1)
        end

        return sum
    end

    return _formalSeriesFromRule(rule)
end

_formalSeries.__index = function (formalSeries, n)
    return formalSeries["rule"](n)
end

polynomialAlgebra.formalSeries = {}

polynomialAlgebra.formalSeries.new = function (rule)
    return _formalSeriesFromRule(rule)
end

polynomialAlgebra.formalSeries.partialSum = function (formalSeries, n)
    return _polynomialFromFormalSeries(formalSeries, n)
end

polynomialAlgebra.formalSeries.inverse = function (formalSeries)
    return _formalSeriesInverse(formalSeries)
end

polynomialAlgebra.formalSeries.derivative = function (formalSeries)
    return _formalSeriesDerivative(formalSeries)
end

polynomialAlgebra.formalSeries.integral = function (formalSeries, c)
    return _formalSeriesAntiderivative(formalSeries, c)
end

return polynomialAlgebra