18.09.2008

18 września (czwartek) - 14.35

Jaro powiedział coś o zadaniach z IOI.

Przepraszam, za żenadę która się zrobiła na kółku.

Dokończenie zadania o ogrodach (Linear Garden)

Definicje

Ciąg — słowo złożone z literek L, P, w którego każdym podsłowie różnica ilości literek L i P nie jest większa niż 2 (tzn. w ogóle w poniższym opisie nie obchodzą nas niepoprawne słowa).

Mówimy, że (poprawny) ciąg jest typu T jeśli dla każdego jego prefiksu różnica L-P test w podanym przedziale w poniższej tabelce.

Typ	Przedział ( L-P )
1	[-2; 2]
2	[-2; 1]
3	[-1; 2]
4	[-2; 0]
5	[-1; 1]
6	[0; 2]

Zauważmy, że pojedynczy ciąg może być wielu typów. W szczególności każdy ciąg jest typu 1.

Graf

(Uwaga! Na rysunku wierzchołki są przenumerowane)

Z wierzchołka X do Y mamy krawędź o etykiecie E, wtedy i tylko wtedy gdy spełnione są oba warunki

dla każdego ogródka typu X, zaczynającego się na E, po usunięciu pierwszego E mamy ogród typu Y.
dla każdego ogródka typu Y, po dopisaniu z przodu E dostajemy ogródek typu X.

Oznaczenia:

L[T] — typ na końcu strzałki wychodzącej z T o etykiecie L, jeśli istnieje
P[T] — typ na końcu strzałki wychodzącej z T o etykiecie P, jeśli istnieje

Zliczanie ciągów danego typu

D[k,T] — liczba ciągów długości k, które są typu T

Aby policzyć D[k,T] korzystamy ze skonstruowanego grafu. Liczbę wszystkich k-słów (czyli słów długości k) typu T możemy policzyć dodając dwie liczby:

Liczbę k-słów typu T zaczynających się na L. Tych słów jest tyle samo, co (k-1)-słów typu L[T] (o ile L[T] istnieje, w przeciwnym razie tych ciągów jest zero). Jeśli nie wierzysz, spróbuj dogłębnie przemyśleć definicję grafu. Jeśli dalej nie wierzysz, miej pretensje i pisz do Accka.
Liczbę k-słów typu T zaczynających się na P, czyli D[k-1,P[T]] (oczywiście o ile P[T] istnieje).

A zatem (o ile L[T] i P[T] istnieją):

D[k,T] = D[k-1,L[T]] + D[k-1,P[T]]

Na samym początku programu możemy sobie stablicować D[k,T] dla wszystkich k i T.

Zliczanie ciągów o danym prefiksie

Ile jest n-elementowych ciągów postaci LPPLLPL*?

Spostrzeżenie 1. Wszystkich n-elementowych ciągów jest D[n,1].
Spostrzeżenie 2. Spośród wszystkich n-elementowych ciągów, D[n-1, L[1]] zaczyna się na literkę L (nie wierzysz? wróć do poprzedniego podrozdziału)
Spostrzeżenie 3. Spośród wszystkich n-elementowych ciągów, które zaczynają się na L, D[n-2, P[L[1]]] ma jako drugą literkę P.
Spostrzeżenie 4. Spośród wszystkich n-elementowych ciągów, które zaczynają się na LP, D[n-3, P[P[L[1]]]] ma jako trzecią literkę P.
…
Spostrzeżenie 8. Wszystkich n-elementowych ciągów, które zaczynają się na LPPLLPL jest D[n-7, L[P[L[L[P[P[L[1]]]]]]]].

L[P[L[L[P[P[L[1]]]]]]] to nic innego jak numer wierzchołka grafu, w którym się znajdziemy startując od jedynki i idąc kolejno po krawędziach: L, P, P, L, L, P, L.

Zliczanie ciągów leksykograficznie mniejszych od danego

Ile jest n-elementowych ciągów leksykograficznie mniejszych od LPPLLPPL?

Tyle, ile w sumie n-ciągów poniższych postaci:
LL* LPL* LPPLLL* (takich jest zero) LPPLLPL*

Oczywiście, aby wyliczyć liczbę ciągów leksykograficznie mniejszych od LPPLLPPL, nie liczymy osobno, w czasie liniowym, każdego z powyższych składników, tylko robimy to sprytniej, łażąc po grafie. Mam nadzieję, że każdy potrafi to wymyślić. Jeśli nie, proszę krzyczeć na Accka i spojrzeć w poniższy kod.

Implementacja

#include <stdio.h>
int graph[7][2]={{1, 2}, {3, 2}, {1, 5}, {6, 4}, {3, 5}, {4, 6}};
int wyn[1000000][7];
char tekst[1000000];
int n, m;
 
int main(void){
    scanf("%d %d %s", &n, &m, tekst);
    for(int i=0; i<n; ++i) tekst[i]=(tekst[i]=='P');
    for(int i=0; i<6; ++i) wyn[0][i]=1;
    for(int i=1; i<n; ++i) for(int j=0; j<6; ++j) wyn[i][j]=(wyn[i-1][graph[j][0]] + wyn[i-1][graph[j][1]]) % m;
    int res=0;
    int state=0;
    for(int i=0; i<n; ++i){
        if(tekst[i]) res=(res+wyn[n-i-1][graph[state][0]]) % m;
        state=graph[state][tekst[i]];
    };
    printf("%d\n", (res+1)%m);
};