1041. Króliczki Jasia [KRO]

Zadanie:
https://pl.spoj.com/problems/KRO

Skrócony opis problemu:

Mając dane 2 początkowe wyrazy ciągu Fibonacciego $a$ i $b$ oraz liczbę $n$ mamy wypisać ostatnią cyfrę $n$-tego wyrazu tego ciągu.

Rozwiązanie naiwne:

Obliczamy ostatnie cyfry dwóch podanych wyrazów, a następnie obliczamy kolejne wyrazy modulo 10 (modulo 10, bo interesują nas tylko ostatnie cyfry, które uzyskuje się z dodawania ostatnich cyfr) aż dojdziemy do $n$-tego.

Np. dla: $a=4, b=4, n=5$: 4, 4, 4+4 = 8, 4+8 = 12 (%10) = 2, 8+2=10 (%10) = 0.

Złożoność: $O(n)$, jako że obliczamy $n$ pierwszych elementów ciągu.

Rozwiązanie sprytne:

Autorem tego rozwiązania jest Filip Czaplicki.

Możemy obliczyć $n$-tą liczbę Fibonacciego dla dwóch dowolnych wyrazów początkowych za pomocą macierzy Fibonacciego. Dla oryginalnego ciągu Fibonacciego wystarczy tylko obliczyć macierz:

$$\begin{bmatrix} 1&1 \\ 1&0 \end{bmatrix}^{n-1}$$

... a następnie wziąć lewą, górną komórkę.

Dla dowolnego ciągu Fibonacciego musimy tylko na koniec spotęgowaną macierz przemnożyć przez wektor

$$\begin{bmatrix} b \\ a \end{bmatrix}$$

...i wziąć górny element.

Należy jeszcze pamiętać, żeby po każdej operacji na macierzy zwracać wynik modulo 10.

Dlaczego to rozwiązanie jest szybsze od poprzedniego? Ano dlatego, że możemy to zrobić w czasie logarytmicznym korzystając z szybkiego potęgowania, który jest dobrze opisany tutaj. Macierz 2x2 można pomnożyć tak jak liczbę, w czasie stałym.

Złożoność: $O(\log n)$, jako że szybkie potęgowanie macierzy działa w czasie logarytmicznym.

Algorytm:

typedef struct
{
    int a, b, c, d;
} matrix;

matrix mul(matrix x, matrix y)
{
    matrix z;
    z.a = (x.a*y.a+x.b*y.c)%10;
    z.b = (x.a*y.b+x.b*y.d)%10;
    z.c = (x.c*y.a+x.d*y.c)%10;
    z.d = (x.c*y.b+x.d*y.d)%10;
    return z;
}

matrix mpow(matrix m, int n)
{
    if(n < 2)
        return m;
    else if(n%2 == 1)
    {
        matrix a;
        a.a = a.b = a.c = 1; a.d = 0;
        return mul(a, mpow(m, n-1));
    }
    else
    {
        matrix a = mpow(m, n/2);
        return mul(a, a);
    }
}

int main()
{
    int n, a, b; // dane
    matrix x;

    x.a = x.b = x.c = 1; x.d = 0;
    get(n, a, b);
    a %= 10; b %= 10;
    if(n == 1)
        print(a);
    else if(n == 2)
        print(b);
    else
    {
        x = mpow(x, n-2);
        print((x.a*b+x.b*a)%10);
    }
}

Rozwiązanie sprytniejsze:

Możemy wykorzystać fakt, że potrzebujemy tylko ostatniej cyfry. Jeśli więc mamy jakieś cyfry $a$, $b$, od których zaczynamy to prędzej czy później znów dojdziemy do dwóch kolejnych liczb, będących nimi. Co więcej, na pewno będzie ich mniej niż 101, gdyż par cyfr jest 100.

Przyjrzyjmy się poprzedniemu przykładowi. Kolejne wyrazy to:

4, 4, 8, 2, 0, 2, 2, 4, 6, 0, 6, 6, 2, 8, 0, 8, 8, 6, 4, 0, 4, 4, ...

Inny przykład:

6, 9, 5, 4, 9, 3, 2, 5, 7, 2, 9, 1, 0, 1, 1, 2, 3, 5, 8, 3, 1, 4, 5, 9, 4, 3, 7, 0, 7, 7, 4, 1, 5, 6, 1, 7, 8, 5, 3, 8, 1, 9, 0, 9, 9, 8, 7, 5, 2, 7, 9, 6, 5, 1, 6, 7, 3, 0, 3, 3, 6, 9, ...

Jeszcze inny:

0, 5, 5, 0, 5, ...

I ostatni:

0, 0, 0, ...

Długości tych ciągów, to odpowiednio: 20, 60, 3, 2. Widzimy, że NWW tych liczb to 60. Okazuje się, że wszystkie ciągi są krótsze od 61 i ich NWW z 60 to 60. Nie umiem tego niestety udowodnić (jeśli ktoś umie, byłbym wdzięczny, gdyby się podzielił). W każdym razie nasz wynik znajduje się w 60 pierwszych elementach ciągu. Robimy więc $n %= 60$ i obliczamy $n$-ty wyraz ciągu.

Ciekawostka: Powtarzanie się wyrazów ciągu Fibonacciego modulo jakaś liczba jest nazywane okresem Pisano.

Złożoność: $O(1)$, gdyż zawsze wykonujemy 60 operacji, co jest stałą liczbą.

Ostateczny algorytm:

int main()
{
    int n, i, tab[61], a, b;

    get(n, a, b);
    tab[1] = a%10; tab[2] = b%10;
    n = (n-1)%60+1; // zamiast n%=10, żeby móc numerować tablicę od 1 i potem wypisać po prostu tab[n]
    for(i = 3; i <= n; ++i)
        tab[i] = (tab[i-1]+tab[i-2])%10;
    print(tab[n]);
}