Cześć mam takie zadanie:
Na drugim kongresie Bajtockiego Towarzystwa Informatyków (nazwanymdla odmiany po prostu spotkaniem) uczestnicy zasiedli dookoła okrągłego stołu. Jeden z uczestników postawił pytanie, na ile sposobów siedzący mogą się przywitać bez wstawania od stołu. Przywitanie takie polega na tym, że każdy uczestnik ściska dłoń co najwyżej jednego swojego sąsiada. Ponieważ uczestnicy kongresu są informatykami teoretykami, poprosili Ciebie o napisanie programu, który policzy dla nich tę liczbę sposobów. Żeby nie operować dużymi liczbami wystarczy, jeżeli podasz im ostatnią cyfrę wyniku.
Wejście
W pierwszym wierszu wejścia znajduje się jedna liczba całkowita n (3 <= n <= 2 · 109 ) oznaczająca liczbę uczestników kongresu.
Wyjście
W pierwszym i jedynym wierszu wyjścia powinna znajdować się jedna cyfra, będąca ostatnią cyfrą szukanej liczby możliwych konfiguracji uścisków dłoni.
Np. dla Wejścia 4 output wynosi 7
I taką odpowiedź:
Rozważmy prostszy problem, w którym pytamy o liczbę konfiguracji uścisków, ale przy podłużnym stole, przy którym zasiada n osób. Niech Fi będzie liczbą konfiguracji przy stole o długości i. Pierwszą osobę możemy sparować z drugą i wtedy dostajemy Fn−2 konfiguracji lub zostawić wolną i wtedy dostajemy Fn−1 konfiguracji, czyli w sumie Fn−1 + Fn−2. W powyższy sposób otrzymujemy ciąg Fibonacciego, gdzie F1 = 1, F2 = 2.
• Wyróżnijmy jedną osobę zasiadającą przy okrągłym stole. Jeśli połączymy ją w parę z lewym sąsiadem, to możemy obliczyć liczbę konfiguracji n − 2 osób zasiadających przy podłużnym stole, podobnie przy połączeniu w parę z prawym sąsiadem. Jeśli nie połączymy jej w parę z nikim, to liczymy liczbę konfiguracji n − 1 osób przy podłużnym stole. Sumarycznie otrzymujemy
2 · Fn−2 + Fn−1 = Fn−2 + Fn konfiguracji.
• Pozostaje pytanie, w jaki sposób szybko obliczać ostatnią cyfrę dowolnej liczby Fibonacciego. Zauważmy, że musi istnieć cykl, w którym cyfry będą się powtarzały, i taki cykl nie przekroczy długości 100 (czyli liczby różnych par cyfr).
No i napisałem taki kod
#include "bits/stdc++.h"
using namespace std;
int main()
{
ios_base::sync_with_stdio(0);
vector <int> fib(101, 0);
fib[0] = fib[1] = 1;
for (int i = 2; i <= 100; i++){
fib[i] = (fib[i-1] + fib[i-2]) % 10; // tablica fib z ostatnimi cyframi ciag fibbonaciego
}
int n;
cin >> n;
n %= 100;
cout << (fib[n] + fib[(100 + n-2) % 100 ]) % 10; // jesli n - 2 < 0 to dodajemy komorke 100 - (n - 2)
// wypisujemy reszte z dzielenia Fn + F(n-2) przez 10
return 0;
}
Tutaj sprawdzam poprawność rozwiązań
Daje błędne odpowiedzi dla:
102
wczytano '3', a oczekiwano '8'
1024
wczytano '2', a oczekiwano '7'
2011011
wczytano '9', a oczekiwano '4'
Gdzie robię błąd?