Informatyczny kącik olimpijski

Wielomian

W tym miesiącu omówię zadanie Wielomian, które pojawiło się na finale Potyczek Algorytmicznych w 2005 roku.

Zadanie 1. Dany jest wielomian $W$ stopnia (co najwyżej) $n,$ zdefiniowany poprzez jego wartości w punktach $0,1,2,...,n.$ Naszym zadaniem jest wyznaczenie wartości tego wielomianu w punkcie $n + 1.$

Oznaczmy współczynniki wielomianu $W$ przez ciąg liczb $a ,a ,...,a , 0 1 n$ gdzie $|ai$ oznacza współczynnik przy $i x .$ Najprostszym sposobem rozwiązania tego zadania jest wyznaczenie współczynników wielomianu $W,$ rozwiązując następujący układ równań liniowych:

⎧⎪⎪ a0 = W(0) ⎪⎪⎪⎪ ⎪⎪⎪⎪ a0 + a1 + a2 +...+ an = W(1) ⎪⎨ a0 + 2a1 + 4a2 + ⋅⋅⋅+ 2nan = W(2) ⎪⎪⎪ ⎪⎪⎪⎪ ⎪⎪⎪⎪ a0 + na1 + n2a2 + ...+ nnan = W(n) ⎩

Można to zrealizować za pomocą metody eliminacji Gaussa. Niestety, ten algorytm jest zbyt powolny, ponieważ wykonuje on $| 3 O(n )$ operacji na liczbach, które mogą rosnąć wykładniczo. Metodę tę można jednak znacznie przyśpieszyć, wykorzystując fakt, że znamy wartości wielomianu $W$ w punktach będących kolejnymi liczbami naturalnymi.

Lemat 1. Istnieje wielomian $|W′$ stopnia co najwyżej $n − 1,$ taki że $|′ W(k) = W(k + 1)− W(k)$ dla $| k ∈ {0,1,...,n}.$

Dowód. Skoro funkcje $W(x)$ oraz $|W(x + 1)$ są wielomianami, to również funkcja $W(x + 1)− W(x)$ jest wielomianem. Współczynnik wielomianu $W(x),$ przy $xn,$ wynosi $a . n$ Natomiast dla wielomianu $|W(x + 1)$ mamy:

a (x + 1)n = a ((n )xn + ( n )xn −1 +...+ (n )x + (n )). n n n n −1 1 0

Korzystając z lematu 1, możemy zredukować stopień wielomianu $|W,$ uzyskując problem równoważny. Aby to zrobić, zdefiniujmy ciąg wielomianów $|P0,...,Pn,$ taki że $Pn = W$ oraz $Pi−1( j) = Pi( j +1) −Pi( j)$ dla $|0 < i ⩽ n$ oraz $|0⩽ j⩽ i.$ Powstały w ten sposób wielomian $P0$ ma stopień $0,$ zatem $|P (1) = P (0). 0 0$ Znając wartość wielomianu $|P 0$ w kolejnym punkcie, możemy obliczyć wartości $Pi(i + 1)$ dla $0 < i ⩽n$ bezpośrednio z definicji ciągu wielomianów $P .$ Obliczając nowe wartości kolejnych wielomianów, za każdym razem do poprzednio otrzymanej wartości dodajemy $|P (i), i$ zatem:

n W(n + 1) = Q Pi(i). i 0

Spróbujmy teraz zapisać $W(n + 1)$ w zależności od wartości $|W(0),...,W(n).$ Skoro jedynymi operacjami, jakie wykonujemy, są dodawanie i odejmowanie, to wszystkie otrzymane liczby będą liniowo zależne od wartości wielomianu $W.$ Możemy, korzystając z definicji ciągu wielomianów $P,$ zapisać:

Pn−1( j) = W( j + 1) −W( j), Pn−2( j) = W( j + 2)− 2⋅W( j+ 1)+ W( j),

oraz w ogólności:

n−i+ j n−i+ j− k n − i Pi( j) = Q (−1) ( )W(k). k j k − j

Zachęcam Czytelnika, aby sprawdził poprawność tego wzoru i spróbował go udowodnić za pomocą indukcji matematycznej. Po wstawieniu tej równości do wzoru otrzymanego w poprzednim akapicie dostajemy:

n n n−k n − i n n n−k i W(n+1) = Q Q (− 1) ( )W(k) = Q Q (−1) ( )W(k). i 0k i k − i k 0i n−k n − k

Lemat 2. Prawdziwa jest tożsamość

n Q (i) = (n +1). i j j j+ 1

Dowód. Udowodnimy ją za pomocą indukcji względem $n.$ Dla $|n = j$ mamy

j i j + 1 Q ( ) = 1 = ( ). i j j j + 1

W kroku indukcyjnym korzystamy z tożsamości:

n+1 i n i n + 1 n + 1 n + 1 n + 2 Q ( ) = Q ( )+ ( ) = ( ) + ( ) = ( ). i j j i j j j j + 1 j j + 1

Na podstawie lematu 2 otrzymujemy dla $| j = n −k$ :

n n W(n + 1) = (− 1)n− k( n + 1 )W(k) = (− 1)n−k(n + 1)W(k). Qk 0 n − k +1 Qk 0 k

Dzięki tożsamości

n+1 (n + 1) = (-k-)(n-−k-+-1) k + 1 k + 1

możemy obliczyć powyższą sumę, wykonując liniową ilość operacji na liczbach całkowitych.

Wartości składników tej sumy mogą być bardzo duże, więc dodatkową trudność w tym zadaniu są operacje na dużych liczbach. Na szczęście potrzebujemy jedynie wykonywać sumowanie dużych liczb oraz mnożenie i dzielenie dużych liczb przez małe. Obie te operacje można łatwo zrealizować w czasie liniowym względem długości liczby. Zatem ostatecznie otrzymujemy złożoność czasową $O(n2).$