Ciąg podobny do ciągu Fibonacciego

Natrafiłem ostatnio na problem algorytmiczny: https://main.edu.pl/pl/archive/pa/2006/spo
Doszedłem do tego jak obliczać ostatnią cyfrę, ponieważ będzie to powtarzający się ciąg o rozmiarze 100.
Jednak liczenie samego ciągu na wzór Fibonacciego nie zwraca mi prawidłowych wyników, wyszedłem z założenia, że gdy przy stole zasiada jedna osoba to nie wita się z nikim więc F[0] = 1, dla dwóch osób będzie to już F[1] = 2 bo mogą się witać lub nie, z kolei dla trzech osób byłoby to F[2] = F[1] + F[0] i tu osiągam już pierwszy zły wynik bo trzy osoby mogą się nie witać wgl lub witać się pojedyńczo co daje kolejne 3 rozwiązania.

A to nie będzie liczba kombinacji dwuelementowych plus jeden?

Nie jestem pewien czy zrozumiałem dobrze, ale jeśli miałyby to być 2 elementowe kombinacje z n elementowego zbioru to nie zostałyby spełnione założenia zadania(witać się mogą osoby siedzące tylko koło siebie oraz nie mogą się witać z dwiema osobami na raz).

Wyślij rozwiązanie modulo 10, to sie Przekonasz:)

Zastanów się jak zamodelować ten problem. Proponuję rozrysować drzewo decyzyjne dla każdego uczestnika. Dla n uczestników drzewo takie ma n poziomów.

Zauważ, że:

1. Jeżeli uczestnik po lewej się z tobą przywitał to ty już nie możesz przywitać się w uczestnikiem po prawej. Tzn. masz tylko jedną możliwą decyzję.
2. Jeżeli uczestnik po lewej się z tobą nie przywitał, to masz 2 opcje - przywitać się albo nie.
3. Ostatniego uczestnika należy traktować specjalnie. Jego wybór jest ograniczony przez wybór pierwszego uczestnika

W efekcie powstanie Ci piękne drzewko, a liczba liści w tym drzewie to wynik. Reguły w drzewie, na podstawie powyższych obserwacji:

1. Drzewo ma n poziomów, liczonych od 0.
2. Poziom w drzewie reprezentuje wszystkie decyzje jakie może podjąć n-ty uczestnik na temat przywitania się z następnym w kolejności uczestnikiem (zapętla się do uczestnika nr 1).
3. Przywitanie się to rozgałęzienie w prawo. Dwa rozgałęzienia w prawo pod rząd są nielegalne.
4. Nie przywitanie się to rozgałęzienie w lewo.
5. Ostatni poziom nie uwzględnia decyzji jaką podjął uczestnik nr 1.
6. Wynikiem jest liczba liści w drzewie minus liczba tych liści na ostatnim poziomie, które reprezentują nielegalne przywitanie się (patrz reguła 5 i 3, jeżeli korzeń rozgałęził się w prawo, to liście, które rozgałęziły się od rodziców w prawo są nielegalne i trzeba je odjąć od wyniku)

Wyprowadź z tych zależności wzór i masz wynik.

Muszę się nad tym zastanowić, przyznam, że trochę to ciężkie dla mnie