Wyzwanie

Biorąc wielomianu po współczynnikach rzeczywistych porządku 1i stopnia n, znaleźć inny wielomian qstopnia co najwyżej ntaki, że (p∘q)(X) = p(q(X)) ≡ X mod X^(n+1), innymi słowy takie, że p(q(X)) = X + h(X)gdzie hjest dowolnym wielomianem ord(h) ≥ n+1. Wielomian qjest jednoznacznie określony przez p.

Dla wielomian p(X) = a(n)*X^n + a(n+1)*X^(n+1) + ... + a(m)*X^mgdzie n <= mi a(n) ≠ 0, a(m) ≠ 0mówimy, njest zamówienie od pi mjest wyższe od p.

Uproszczenie : Możesz założyć, że pma współczynniki całkowite, i a(1)=1(tak p(X) = X + [some integral polynomial of order 2]). W tym przypadku qma również współczynniki całkowite.

Celem tego uproszczenia jest uniknięcie problemów z liczbami zmiennoprzecinkowymi. Istnieje jednak niecałkowity przykład do celów ilustracyjnych.

Przykłady

• Zastanów się nad serią Taylora, exp(x)-1 = x + x^2/2 + x^3/6 + x^4/24 + ...a ln(x+1) = x - x^2/2 + x^3/3 - x^4/4 + ...potem oczywiście ln(exp(x)-1+1)= x. Jeśli po prostu rozważyć wielomiany stopnia 4 Taylor z tych dwóch funkcji możemy uzyskać z notacją od dołu (patrz testami) p = [-1/4,1/3,-1/2,1,0]i q = [1/24, 1/6, 1/2, 1,0]i(p∘q)(X) ≡ X mod X^5

• Rozważ wielomian p(X) = X + X^2 + X^3 + X^4. A q(X) = X - X^2 + X^3 - X^4więc dostaniemy

  (p∘q)(X) = p(q(X)) = X - 2X^5 + 3X^6 - 10X^7 +...+ X^16 ≡ X mod X^5
  

Przypadki testowe

W tym przypadku wielomian wejściowy i wyjściowy są zapisywane jako listy współczynników (ze współczynnikiem monomialu najwyższego stopnia najpierw, a stałym składnikiem jako ostatnim):

p = [4,3,2,0];  q=[0.3125,-.375,0.5,0]

Zintegrowane przypadki testowe:

p = [1,0]; q = [1,0]

p = [9,8,7,6,5,4,3,2,1,0]; q = [4862,-1430,429,-132,42,-14,5,-2,1,0]

p = [-1,3,-3,1,0]; q = [91,15,3,1,0]

Python 2 + sympy, 128 bajtów

Lokalnie odwracamy wielomian przyjmując, że q (x) = x, łącząc go z p, sprawdzając współczynnik dla x ² i odejmując go od q. Powiedzmy, że współczynnik wynosił 4, a następnie nowy wielomian staje się q (x) = x - 4x ² . Następnie ponownie komponujemy to za pomocą p, ale szukamy współczynnika dla x ³ . Itp...

from sympy import*
i=input()
p=Poly(i,var('x'));q=p*0+x
n=2
for _ in i[2:]:q-=compose(p,q).nth(n)*x**n;n+=1
print q.all_coeffs()

Mathematica, 45 bajtów

Normal@InverseSeries[#+O@x^(#~Exponent~x+1)]&

Tak, Mathematica ma do tego wbudowane ...

Nienazwana funkcja przyjmująca jako dane wejściowe wielomian w zmiennej x, na przykład -x^4+3x^3-3x^2+xdla ostatniego przypadku testowego, i zwracająca wielomian o podobnej składni, na przykład x+3x^2+15x^3+91x^4dla ostatniego przypadku testowego.

#+O@x^(#~Exponent~x+1)zamienia wejście #w obiekt szeregu mocy, obcięty o stopień #; InverseSeriesrobi to, co mówi; i Normalprzekształca wynikową skróconą serię mocy z powrotem w wielomian. (Możemy zapisać te początkowe 7 bajtów, jeśli odpowiedź w formularzu byłaby x+3x^2+15x^3+91x^4+O[x]^5akceptowalna. Rzeczywiście, gdyby był to akceptowalny format zarówno dla danych wejściowych, jak i wyjściowych, wówczas InverseSeriessam byłby rozwiązaniem 13-bajtowym.)

JavaScript (ES6), 138 bajtów

a=>a.reduce((r,_,i)=>[...r,i<2?i:a.map(l=>c=p.map((m,j)=>(r.map((n,k)=>p[k+=j]=m*n+(p[k]||0)),m*l+(c[j]||0)),p=[]),c=[],p=[1])&&-c[i]],[])

Port odpowiedzi @ orlp. I / O ma postać tablic współczynników w odwrotnej kolejności, tzn. Pierwsze dwa współczynniki to zawsze 0 i 1.

Pari / GP , 29 bajtów

p->Pol(serreverse(p+O(x^#p)))

Wypróbuj online!