Cześć.

Jestem w trakcie prób zrobienia zadania Podciągi arytmetyczne ( http://main.edu.pl/pl/archive/ilocamp/2011/art ). Nie byłem w stanie samemu wymyślić wzorcowego rozwiązania, dlatego postanowiłem je wyczytać (w załącznikach zamieszczam skan do tego rozwiązania).

Nie rozumiem w tym rozwiązaniu paru rzeczy dotyczących haszowania. Jest napisane, że każdy wierzchołek odpowiadający za przedział [a,b] zawiera hasz podsłowa znajdującego się w tym przedziale, oraz jest podany wzór przedstawiający sposób wyliczania haszu. W tym wzorze jest liczba p, która według mnie przedstawia podstawę do haszu. Jaką liczbę powinno się podstawić pod p ? Wydaje mi się, że skoro słowo jest ciągiem zero-jedynkowym, to p = 2. Mam rację ?

Drugą rzeczą, której nie rozumiem jest to, że jeśli mamy wierzchołek przedstawiający duży przedział, np. [1,200000], to podczas wyliczania haszu dla tego przedziału trzeba by było wyliczyć potęgę 2199999 (zakładam, że faktycznie p = 2). Co mam zrobić w takim momencie ? Wyliczać resztę z dzielenia przez jakąś dużą liczbę pierwszą ? Jest napisane, że należy należy wyliczyć wszystkie potęgi p przed rozpoczęciem wykonywania właściwego algorytmu, więc powinienem wyliczyć reszty wszystkich potęg dwójki do 2199999 z dzielenia przez jakąś liczbę pierwszą ? To byłoby poprawne ?