Wielki Zderzacz Termionów

Autorzy zadań do Potyczek Algorytmicznych trzymają naprawdę wysoki poziom. Jak oni wymyślają te zadania? Nie wiem.

Krótkie streszczenie treści zadania

W zadaniu Wielki Zderzacz Termionów mamy trzy rodzaje cząstek elementarnych: Czerwony (C), Zielony (Z) i Niebieski (N). Cząstki elementarne ustawia się w rzędzie i reagują ze sobą. Dwa sąsiednie termiony Czerwone mogą zamienić się w jeden Zielony, a dwa sąsiednie Zielone w jeden Czerwony. Niebieski to taki joker, który zamienia się w Czerwony lub Zielony. Niebieskie zamieniają się jako pierwsze i w efekcie dostajemy ciąg złożony z Czerwonych i Zielonych. Ciąg złożony z Czerwonych i Zielonych nazywamy prawidłowym jeśli istnieje kolejność łączenia termionów w taki sposób, aby na końcu otrzymać jeden termion.

W zadaniu pytano o to na ile różnych sposobów można zamienić Niebieskie termiony na Czerwone i Zielone, aby otrzymać ciąg prawidłowy. Następnie na ciągu przeprowadzamy q operacji polegających na zastąpieniu pewnego termionu przez inny. Po każdej takiej operacji należało ponownie odpowiedzieć na to pytanie. Liczbę sposobów podajemy modulo 10⁹+7.

Ciągi alternujące

W pierwszej części rozwiązania zastanowimy się, kiedy ciąg złożony jedynie z termionów C i Z jest poprawny.

Ciąg nazywamy alternującym, jeśli na przemian występują w nim termiony Czerwone i Zielone. Na przykład ciąg CZCZCZC i ZCZ są alternujące, natomiast ciągi ZZCC i CZCZZC nie są alternujące.

Spostrzeżenie: W ciągu termionów nie możemy wykonać żadnej operacji wtedy i tylko wtedy, gdy ciąg jest alternujący. Dla każdego n istnieją dokładnie dwa ciągi alternujące.

Niech #C #Z i #N oznacza kolejno: liczbę Czerwonych, Zielonych i Niebieskich termionów w ciągu. Ponadto długość ciągu oznaczmy jako n.

Jeśli n = 1 to każdy ciąg (są dwa takie ciągi: C oraz Z) jest poprawny. W każdym z nich możemy wykonać zero operacji i otrzymamy w ten sposób jeden termion na końcu.

Lemat: Dla n ≥ 2 ciąg o n elementach NIE jest poprawny wtedy i tylko wtedy, gdy jest alternujący lub gdy 3 dzieli n + #C.

Dowód (indukcyjny): Istnieją 4 ciągi dla n = 2: CC, CZ, ZC oraz ZZ. Ciągi CC oraz ZZ są poprawne, a ciągi CZ oraz ZC są niepoprawne. Policzmy dla każdego z tych ciągów ile wynosi n + #C:

• Dla CC mamy #C = 2, a zatem n + #C = 4, 3 nie dzieli n + #C i ciąg jest poprawny
• Dla CZ mamy #C = 1, a zatem n + #C = 3, 3 dzieli n + #C i ciąg nie jest poprawny
• Dla ZC mamy #C = 1, a zatem n + #C = 3, 3 dzieli n + #C i ciąg nie jest poprawny
• Dla ZZ mamy #C = 0, a zatem n + #C = 2, 3 nie dzieli n + #C i ciąg jest poprawny

Ponadto ciągi CZ oraz ZC są alternujące, więc lemat jest prawdziwy dla n = 2.

Weźmy dowolne n > 2. Jeśli ciąg jest alternujący to nie da się wykonać żadnego ruchu i ciąg nie jest poprawny. Załóżmy więc, że ciąg nie jest alternujący, możemy wykonać zatem w nim pewien ruch. Rozważmy dwa przypadki:

Jeśli 3 dzieli n + #C to wykonajmy pewien dozwolony ruch. Niech n' oraz #C' oznaczają odpowiednio długość ciągu oraz liczbę Czerwonych termionów po wykonaniu tego ruchu. Jeśli zamieniliśmy dwa termiony Zielone na jeden Czerwony, to liczba termionów zmniejszyła się o jeden, a liczba termionów Czerwonych wzrosła o jeden: n' = n - 1 oraz #C' = #C + 1. Zatem 3 dzieli n' + #C' bo n' + #C' = n-1 + #C + 1 = n + #C. Jeśli z kolei zamienimy dwa termiony Czerwone na jeden zielony, to liczba Czerwonych termionów zmniejszyła się o dwa: n' = n - 1 oraz #C = #C - 2. Zatem 3 dzieli n' + #C bo n' + #C = n - 1 + #C - 2 = n + #C - 3.

Dowód gdy 3 nie dzieli n + #C jest niemal identyczny (wykonanie jednego kroku nie zmienia reszty z dzielenia przez trzy wartości n + #C). Pozostaje nam udowodnić, że po wykonaniu ruchu nie trafimy na ciąg alternujący. Bez straty ogólności powiedzmy, że zamieniliśmy dwa termiony C i otrzymaliśmy ciąg alternujący ...CZCZCZC... gdzie pogrubiony termion Z to termion nowopowstały. Zatem ciąg przed zamianą wyglądał tak: ...CZCCCCZC... i zamiast pogrubionych termionów mogliśmy zamienić te termiony: ...CZCCCCZC... otrzymując ciąg ...CZZCCZC..., który nie jest alternujący. Sztuczka nie zadziała jeśli n = 2, ale założyliśmy, że n > 2. Nie zadziała też jeśli n = 3, ale wtedy ciąg wygląda tak: CCC (lub tak ZZZ) i w tym przypadku 3 dzieli n + #C (a założyliśmy że nie dzieli). Co kończy dowód.

Pytanie: Czy wystarczy nam warunek o tym, że 3 dzieli n + #C? Innymi słowy: czy o ciągach alternujących możemy zapomnieć? No cóż… i tak i nie… To pytanie może wydawać się naiwne, ale jest ważne, bo za chwilę będziemy zliczać ile ciągów poprawnych może postać po zamianie termionów Niebieskich na termiony C i Z i musimy się upewnić, że żadnych z ciągów nie policzymy dwukrotnie.

Lemat: O ciągach alternujących możemy zapomnieć dla n parzystych i nie możemy o nich zapominać dla n nieparzystych.

Dowód: Rozważamy dwa przypadki. W pierwszym z nich załóżmy, że n jest parzyste i niech k będzie taką liczbą naturalną, że n = 2k. Wtedy w każdym ciągu alternującym #C = k i #Z = k. Zatem n + #C = 2k + k = 3k, zatem 3 dzieli n + #C.

Jeśli n jest nieparzyste, to niech k będzie taką liczbą naturalną, że n = 2k + 1. Wtedy #C jest równe albo k albo k + 1 wtedy n + #C jest równe albo 2k + 1 + k = 3k + 1 albo 2k + 1 + k + 1 = 3k + 2. W żadnym z tych przypadków 3 nie dzieli n + #C. Co kończy dowód.

W tym rozdziale dogłębnie przeanalizowaliśmy ciągi złożone z termionów C i Z. Pomoże to nam zliczyć liczbę sposobów zamian termionów Niebieskich po których ciąg jest poprawny.

Termiony Niebieskie

Załóżmy teraz, że mamy podany już ciąg termionów wraz z termionami Niebieskimi. Aby móc obliczyć na ile sposobów można zamienić termiony Niebieskie, aby otrzymać ciąg poprawny potrzebujemy znać:

• długość ciągu
• liczbę Czerwonych termionów (#C)
• liczbę Niebieskich termionów (#N)
• czy ciąg można zamienić na ciąg alternujący postaci CZCZ...
• czy ciąg można zamienić na ciąg alternujący postaci ZCZC...

Długość ciągu się nie zmienia. Liczbę Czerwonych i Niebieskich termionów można łatwo aktualizować gdy zmienia się ciąg (przypominam: w zadaniu ciąg będzie się zmieniał w ten sposób, że jeden termion w ciągu zostanie zamieniony na inny). W jaki sposób można łatwo aktualizować to czy ciąg można zamienić na ciąg alternujący? Jest to dość prosta i dobrze znana sztuczka: zamiast pamiętać czy się da czy się nie da, pamiętamy ile termionów przeszkadza nam do tego, aby ciąg można było zamienić na ciąg alternujący. Dla przykładu w ciągu CZNC istnieje jeden termion, który przeszkadza ciągowi w byciu ciągiem alternującym CZCZ. Innymi słowy: ilość termionów, które nam przeszkadzają to liczba termionów Z stojących na miejscu, gdzie powinno stać C oraz liczba termionów C, które stoją tam, gdzie stać powinno Z. Taką liczbę łatwo uaktualniać z każdą zmianą ciągu, a aby sprawdzić czy ciąg można zamienić na alternujący, wystarczy sprawdzić czy ta wartość jest równa zero.

Liczbę sposobów na które można zamienić termiony N (na ciągi poprawne i niepoprawne) to po prostu 2^#N. Wartość tą możemy policzyć za pomocą algorytmu szybkiego potęgowania. Następnie możemy odjąć od tej wartości ciągi niepoprawne. Aby to zrobić musimy policzyć na ile sposobów da się wybrać z #N k termionów, aby k miało odpowiednią resztę z dzielenia przez 3. Dla przypomnienia: liczba możliwych wyborów k termionów spośród n, jest równa symbolowi Newtona C(n, k). Zatem chcemy umieć liczyć następujące sumy:

• S(n, 0) := C(n, 0) + C(n, 3) + C(n, 6) + … + C(n, 3 ⌊n /3⌋)
• S(n, 1) := C(n, 1) + C(n, 4) + C(n, 7) + … + C(n, 3 ⌊n /3⌋ + 1)
• S(n, 2) := C(n, 2) + C(n, 5) + C(n, 8) + … + C(n, 3 ⌊n /3⌋ + 2)

Nie jesteśmy niestety tych wzorów po prostu policzyć w ten sposób, ze względu na złożoność naszego rozwiązania. Na szczęście te wzory można policzyć dużo łatwiej:

• S(n, 0) = (2ⁿ + a(n+1)) / 3
• S(n, 1) = (2ⁿ + a(n+5)) / 3
• S(n, 2) = (2ⁿ + a(n+3)) / 3

Gdzie ciąg a = (1, 2, 1, -1, -2, -1, 1, 2, 1, -1, -2, -1, 1, 2, 1, -1, -2, -1, ... ) (ciąg jest okresowy, okres równy 6). Ponieważ ciąg chcemy liczyć modulo 10⁹+7 musimy policzyć modularną odwrotność 3 (jest ona równa 333333336). 2 podniesione do potęgi n liczymy za pomocą szybkiego potęgowania.

Nie zapominajmy o tym, że jeśli n jest nieparzyste, musimy odjąć jeszcze ciągi alternujące jeśli można je uzyskać oraz o tym, że dla n = 1 ciągi alternujące tworzą ciągi poprawne.