Omówienie zadania Wielomian (III etap XXV OI)

W zadaniu tym Bajtazar dostał pewien wielomian o \(n\) współczynnikach całkowitych oraz liczbę \(q\) i ma obliczyć wartość tego wielomianu dla \(n\) kolejnych potęg liczby \(q\), a także sumę tych wszystkich wartości. Ponieważ potęgi liczb całkowitych mogą rosnąć bardzo szybko, standardowo wyniki należy podać modulo pewna liczba \(m\). Następnie w treści mamy podane pewne własności, które muszą spełniać liczby \(n\), \(q\) i \(m\), a które, jak sugeruje Bajtazar, będą kluczowe przy szybkim obliczaniu odpowiedzi.

Podzadanie 1

Bardzo łatwo jest podać rozwiązanie działające w czasie \(O(n^2)\). Wystarczy, że na początku w czasie \(O(n)\) policzymy sobie wszystkie potrzebne potęgi liczby \(q\), a następnie obliczymy wartości wielomianu niezależnie dla każdej z potęg. Zrobimy to w czasie \(O(n)\) albo korzystając ze schematu Hornera, albo na boku w dodatkowej zmiennej licząc kolejne potęgi \(x\) i domnażając je przez kolejne współczynniki.

Częściowe rozwiązanie (obliczanie sumy)

Dla kolejnych podzadań będziemy musieli zaproponować coś szybszego. Podejrzane jest jeszcze, że oprócz tego, że mamy wypisywać wszystkie wartości, to proszą nas również o ich sumę. Jest tak, bo za wypisanie samej sumy można uzyskać \(40\%\) punktów za test. To dość mocno sugeruje, że obliczenie sumy musi być znacznie prostsze niż obliczenie poszczególnych wartości. Zacznijmy od przyjrzenia się, jak szybko możemy obliczyć sumę.

Mamy nasz wielomian, który możemy w sposób zwarty zapisać za pomocą notacji z sumą: \[W(x) = \sum_{i=0}^{n-1} a_i x^i.\] Chcemy teraz obliczyć sumę wartości wielomianu w kolejnych potęgach \(q\), co także możemy zapisać za pomocą sumy: \[S = \sum_{i=1}^{n} W(q^i).\] Rozpiszmy ją, podstawiając do wzoru na \(S\) wzór na \(W\), a następnie zmieniając kolejność sumowania i wyciągając współczynnik \(a_k\) przed wewnętrzną sumę: \[S = \sum_{i=1}^{n} \sum_{k=0}^{n-1} a_k (q^i)^k = \sum_{k=0}^{n-1} a_k \sum_{i=1}^n q^{ik}.\] Dostajemy tym samym całkiem przyjemny wzór na \(S\), w którym każdy współczynnik wielomianu \(a_k\) jest mnożony przez pewną sumę złożoną jedynie z potęg liczby \(q\).

Przyjrzyjmy się zatem, jak szybko obliczać takie sumy potęg. W tym celu skorzystamy w końcu z własności liczb \(n\), \(m\) i \(q\). Pierwsza własność jest taka, że \(n\) musi być potęgą dwójki, a druga własność jest taka, że reszta z dzielenia \(q^n\) przez \(m\) musi być równa \(1\). Przyjrzyjmy się, co tak naprawdę oznacza ta druga własność. Ponieważ będziemy zakładać tutaj, że wszystkie obliczenia prowadzimy modulo \(m\), zatem możemy ją zapisać w postaci \(q^n = 1\).

W naszym wzorze liczba \(q\) jest podnoszona do potęgi \(i \cdot k\), więc te wykładniki mogą być nawet rzędu \(n^2\). Zobaczmy zatem, jak wyglądają większe potęgi liczby \(q\). Potęgę \(q^{\alpha n+ \beta}\) dla \(0\leq \beta < n\) możemy zapisać jako \((q^n)^\alpha \cdot q^\beta\), a ponieważ \(q^n\) jest równe \(1\), więc będzie to po prostu \(q^\beta\). Zatem widać, że kolejne potęgi liczby \(q\) (poczynając od \(q^0\)) powtarzają się w cyklu o długości \(n\), zawierającym potęgi od \(q^0\) do \(q^{n-1}\).

W szczególności, ponieważ \(q^n = q^0\), to w naszych wzorach sumy, które idą od \(1\) do \(n\), możemy zmienić na sumy idące od \(0\) do \(n-1\), co spowoduje, że wszystkie sumy będziemy iterowali od \(0\) do \(n-1\).

Przyjmijmy sobie \(n=8\) i popatrzmy sobie na sumy \(\sum_{i=0}^{n-1} q^{ik}\) dla różnych wartości \(k\):

\(k\)
0	0	0	0	0	0	0	0	0
1	0	1	2	3	4	5	6	7
2	0	2	4	6	0	2	4	6
3	0	3	6	1	4	7	2	5
4	0	4	0	4	0	4	0	4
5	0	5	2	7	4	1	6	3
6	0	6	4	2	0	6	4	2
7	0	7	6	5	4	3	2	1

W tabelce wypisaliśmy sobie dla początkowych \(k\), dla jakich wykładników sumujemy potęgi liczby \(q\). W przypadku \(k=0\) mamy specjalny przypadek, w którym sumujemy same wykładniki \(0\). W przypadku \(k=1\) mamy po prostu sumę kolejnych wykładników. Ciekawie zaczyna się już od \(k=2\): tym razem mnożymy wszystkie wykładniki razy \(2\), przy czym, ponieważ tak jak powiedzieliśmy przed chwilą, te wykładniki zacyklają się z cyklem \(n\), to znaczy ich wielkości również bierzemy modulo \(n\). Tak więc dostaniemy, że piątym wykładnikiem nie będzie \(8\), tylko \(0\). Zatem dla \(k=2\) ten ciąg wykładników rozbija nam się na dwa takie same podciągi \(0, 2, 4, 6\).

W przypadku \(k=3\) wykładniki wydają się być w dość przypadkowej kolejności, ale możemy zauważyć, że występują tutaj wszystkie liczby od \(0\) do \(7\). Wobec tego suma potęg będzie identyczna jak w przypadku \(k=1\). Z kolei w przypadku \(k=4\) mamy już rozbicie na \(4\) takie same podciągi zawierające wykładniki \(0\) i \(4\).

W przypadku \(k=5\) i \(k=7\) mamy znowu przegląd wszystkich wykładników, czyli suma będzie taka sama jak dla \(k=1\). Natomiast w przypadku \(k=6\) mamy podział na dwa takie same podciągi. Ponieważ zbiór wykładników jest taki sam jak w przypadku \(k=2\), wobec tego suma potęg również będzie taka sama jak suma potęg dla \(k=2\). Widzimy w szczególności, że choć mamy \(8\) współczynników wielomianu, to mamy tylko \(4\) różne sumy, przez które będziemy te współczynniki mnożyli.

Na przykład dla \(k=1\), \(3\), \(5\) i \(7\) będzie to taka sama suma, ponieważ w każdym z tych przypadków mamy pełną listę wykładników. Te pełne listy nieprzypadkowo występują wtedy, kiedy \(k\) jest liczbą nieparzystą, ponieważ w liście takiej bierzemy kolejne wielokrotności liczby \(k\) modulo \(n\). Jeżeli \(k\) i \(n\) są względnie pierwsze, czyli ich największy wspólny dzielnik jest równy \(1\), to wtedy zawsze uzyskamy pełną listę \(n\) różnych wartości.

W przeciwnym wypadku, jeżeli przyjmiemy sobie, że \(d\) jest największym wspólnym dzielnikiem (NWD) liczb \(n\) i \(k\), to wtedy ciąg wielokrotności rozpadnie nam się na \(d\) grup. W każdej grupie będziemy mieli \(n/d\) wielokrotności, a poza tym każda grupa będzie wyglądać tak samo i będzie zawierać wszystkie wielokrotności liczby \(d\). W końcu, jeżeli przypomnimy sobie drugą własność z treści zadania, a mianowicie, że liczba \(n\) musi być jakąś potęgą dwójki, czyli \(n=2^N\) dla pewnego \(N\), to liczba kandydatów na NWD jest mocno ograniczona, bo mogą być to jedynie wszystkie potęgi dwójki od \(1\) do \(2^N\). Zatem liczba tych kandydatów będzie równa \(O(\log n)\).

Tak więc, skoro mamy logarytmiczną liczbę różnych sum, przez które będziemy mnożyć współczynniki wielomianu, możemy wprost w czasie \(O(n)\) wyznaczyć każdą z tych sum, zajmie to nam czas \(O(n \log n)\), a następnie przemnażamy współczynniki przez odpowiednie sumy. Żeby wyznaczyć, przez którą sumę mamy przemnożyć współczynnik \(a_k\), liczymy sobie NWD liczb \(k\) oraz \(n\). Jeżeli zastosujemy tutaj algorytm Euklidesa, takie obliczenie wykonamy w czasie \(O(\log n)\), więc ostateczne sumowanie również zajmie nam czas \(O(n \log n)\).

Tym sposobem pokazaliśmy prosty algorytm, który w czasie \(O(n \log n)\) umie obliczyć sumę wymaganych wartości wielomianu i w połączeniu z algorytmem brutalnym dla pierwszego podzadania pozwalało to zdobyć na zawodach \(50\%\) punktów za to zadanie.

Pełne rozwiązanie

Przejdźmy teraz do rozwiązania pełnej wersji zadania, w której zarówno mamy długi wielomian, jak i mamy policzyć jego wartość we wszystkich kolejnych punktach. Ponieważ \(n\) może być rzędu miliona, a w przypadku sumy zaproponowaliśmy algorytm \(O(n \log n)\), więc tutaj też będziemy celowali w algorytm o takiej złożoności czasowej.

Ponieważ \(n\) jest potęgą dwójki, więc ciąg o takiej długości można podzielić na dwie równe połowy, a każdą z nich rekurencyjnie można również równo dzielić. To sugeruje, że być może warto przyjrzeć się, czy naszego zadania nie dałoby się zrobić, korzystając z metody dziel i zwyciężaj. W tej metodzie dzielimy nasz problem na dwa podproblemy, o połowę mniejszych rozmiarach. Rekurencyjnie znajdujemy rozwiązania dla podproblemów, a na końcu rozwiązania dla podproblemów łączymy w rozwiązanie dla oryginalnego problemu.

W naszym przypadku musimy jednak uważać, co stanowi o rozmiarze naszego problemu. Liczba \(n\) oznacza bowiem jednocześnie długość naszego wielomianu, jak i liczbę punktów, w których chcemy policzyć jego wartość. Aby zatem uzyskać podproblem rozmiaru \(n/2\), będziemy musieli zarówno o połowę ograniczyć liczbę współczynników, jak i też liczbę punktów, w którym będziemy taki mniejszy wielomian obliczać. Wydaje się, że ze współczynnikami nie ma większego problemu, bo możemy nasz wielomian \(W\) przedstawić jako sumę dwóch wielomianów, z których każdy będzie miał \(n/2\) współczynników.

Na przykład pierwszy wielomian może zawierać połowę mniejszych współczynników, a drugi połowę większych współczynników. Problematyczne wydaje się jednak ograniczenie liczby punktów, w których mamy obliczanie mniejsze wielomiany. Ale przypomnijmy, że punkty, w których obliczamy ten wielomian, są kolejnymi potęgami liczby \(q\). Co więcej, przy rozwiązywaniu zadania dla sumy, mieliśmy już taką sytuację, w której te potęgi układały nam się w dwie identyczne grupy, każda zawierająca \(n/2\) potęg.

Będzie tak, jeżeli zamiast \(n\) potęg liczby \(q\), rozważymy \(n\) potęg liczby \(q^2\). Ponieważ wykładniki bierzemy modulo \(n\), taki ciąg tak naprawdę rozpadnie nam się na dwa identyczne ciągi, zawierające \(n/2\) potęg liczby \(q^2\).

Kluczowy pomysł

Teraz nadszedł czas na kluczowy pomysł, który przestawimy na przykładzie wielomianu długości \(n=8\): \[W(x) = a_0 + a_1 x + a_2 x^2 + a_3 x^3 + a_4 x^4 + a_5 x^5 + a_6 x^6 + a_7 x^7\]

Jeżeli z naszego wielomianu \(W(x)\) wyciągniemy wszystkie współczynniki o indeksach parzystych, to znaczy takie, które stoją przy parzystych potęgach \(x\), to wyznaczenie wartości takiego wielomianu \(W_P(x)\) dla potęg liczby \(q\) możemy sprowadzić do wyznaczenia wartości analogicznego wielomianu \(V_P(x)\), w którym potęgi wszystkich \(x\) zostały zmniejszone o połowę, dla potęg liczby \(q^2\):

\[W_P(x) = a_0 + a_2 x^2 + a_4 x^4 + a_6 x^6\] \[V_P(x) = a_0 + a_2 x + a_4 x^2 + a_6 x^3\]

Jest tak dlatego, że \(W_P(q^k) = V_P(q^{2k})\). A ponieważ w przypadku tego drugiego wielomianu będziemy liczyć wartości w potęgach liczby \(q^2\), zatem mamy tu jedynie \(n/2\) różnych potęg, dla których potrzebujemy obliczyć wartość wielomianu \(V_P\). Tak więc rzeczywiście policzenie wartości wielomianu \(V_P\) w potęgach liczby \(q^2\) stanowi podproblem o połowę mniejszego rozmiaru, bo mamy tutaj \(n/2\) współczynników oraz mamy \(n/2\) punktów, w których chcemy wartość tego wielomianu policzyć.

Teraz weźmiemy pozostałe współczynniki naszego wielomianu, te o indeksach nieparzystych i w podobny sposób spróbujemy z nich zbudować podproblem o połowę mniejszego rozmiaru. Zrobimy to rozważając wielomian \(V_N(x)\), który powstaje z wielomianu \(W_N(x)\) dla nieparzystych współczynników poprzez podzielanie wszystkiego przez \(x\), a następnie obniżenie wszystkich potęg \(x\) o połowę:

\[W_N(x) = a_1 x + a_3 x^3 + a_5 x^5 + a_7 x^7\] \[V_N(x) = a_1 + a_3 x + a_5 x^2 + a_7 x^3\]

Będziemy wobec tego mieli spełniony wzór \(W_N(q^k) = q^k \cdot V_N(q^{2k})\). I znowu rozmiar wielomianu \(V_N\) jest połową rozmiaru oryginalnego wielomianu oraz będziemy go wyliczać w \(n/2\) punktach.

Podsumowując, rozwiązanie jest następujące. Dany wielomian o \(n\) współczynnikach, dla którego chcemy policzyć jego wartość w \(n\) potęgach liczby \(q\), rozdzielimy na dwa krótsze wielomiany złożone odpowiednio ze współczynników o indeksach parzystych i nieparzystych i obliczamy wartości każdego z nich w \(n/2\) potęgach liczby \(q^2\). Te dwa problemy rozwiązujemy rekurencyjnie.

A następnie wszystkie \(n\) wartości dla wielomianu \(W\) obliczamy, korzystając z \(n/2\) wartości dla wielomianów \(V_P\) i \(V_N\):

\[W(q^k) = W_P(q^k) + W_N(q^k) = V_P(\alpha) + q^k \cdot V_N(\alpha)\] Korzystamy z faktu, że \(\alpha = q^{2^k} = (q^2) ^{k \bmod n/2}\), tak więc \(k\)-ta wartość obliczana dla wielomianu \(W\) będzie korzystała z wartości w wielomianach \(V_P\) i \(V_N\) o indeksie \(k \bmod n/2\).

Oczywiście bazą tej rekurencji będzie przypadek, w którym \(n\) jest równe \(1\), czyli wielomian \(W\) ma tylko jeden współczynnik \(a_0\). Wartość takiego wielomianu dla dowolnego punktu będzie równa \(a_0\).

Złożoność czasowa

Pozostaje jedynie wyznaczyć złożoność czasową naszego rozwiązania. W tym celu musimy rozwiązać rekurencję na czas działania rozwiązania dla problemu rozmiaru \(n\). Na początek taki problem dzielimy na dwa podproblemy rozmiarów \(n/2\) i oba rozwiązujemy rekurencyjnie. Następnie złączamy wyniki tych podproblemów, wykonując jedną pętlę działającą w czasie \(O(n)\): \[T(n) = 2T(n/2) + O(n).\]

Takie równanie rekurencyjne jest spełnione dla wielu algorytmów korzystających z metody dziel i zwyciężaj, na przykład dla algorytmu sortowania przez scalanie, i rozwiązanie tego równania to złożoność czasowa \(T(n) = O(n \log n)\).

Na koniec warto dodać, że metoda, której użyliśmy do rozwiązania naszego zadania, jest stosowana w jednym z najważniejszych algorytmów numerycznych (a mianowicie w szybkiej transformacji Fouriera), szeroko stosowanym, m.in. w cyfrowym przetwarzaniu sygnałów.