Jaś i jego klawiatura - kombinacje haseł

Witam. Mam problem z tym oto zadaniem:

https://sio2.staszic.waw.pl/c/olimpijskie-kolko-informatyczne3/p/klawiatura/1194/

Według mojego rozumowania algorytm jest następujący:

Mamy te pary liter które nie mogą kolo siebie stać:
(a, b), (b, c), (c, a), (f, g)

Kolejno i-lierowe hasła:
(------------------------------------------------)
Hasło 1-literowe:
Mamy 26 kombinacji (a, b, c , ... , z)
(------------------------)
Hasło 2-literowe:
litera a: (aa, ac, ad, ... , az) -> 25 kombinacji
litera b (ba, bb,, ... , bz) -> 25 kombinacji

To samo dla reszty liter które nie mogą kolo siebie stać(dla c i f).

Pozostałe litery mają po 26 kombinacji, czyli całkowita liczba kombinacji z wykluczeniem haseł z literami które nie mogą kolo siebie stać wynosi:
25x4 + 26x22 = 672
(--------------------------------------------------------------)
Hasło 3-literowe:
To co w nawiasie to kombinacje 2-literowe.
litera a:
a(aa, ac, ..., az)
a(ba, bb, bd, ...) -> musimy wyrzucić wszystkie kombinacje 2-literowe dla litery 'b'(dlatego bo po znaku 'a' nie może występować litera 'b'). Czyli dla litery 'a' usuwam:
672(ilość wszystkich kombinacji haseł 2-literowych)
(-)
25(ilość kombinacji 2-literowej tylko dla litery 'b')
(=)
647 -> ilość kombinacji haseł 2-literowych jakie mogą nastąpić po literze 'a'.

To samo dla każdej pary opisanej w zadaniu(tzn. tej pierwszej litery z pary).

Dla pozostałych ilość kombinacji to po prostu 672.

Sumując to wszystko wychodzi:
4x647 + 22x672 = 17372;
(--------------------------------------------)
Hasło 4-literowe:
a:
a(aaa, aac, ..., aaz)
a(baa, bab...) -> usuwam wszystkie kombinacje 3-literowe dla znaku 'b'. Czyli dla litery 'a' i każdej z pary:
17372(łączna suma kombinacji haseł 3-literowych)
(-)
647(ilość kombinacji haseł z litera na początku z danej pary wykluczonej)
(=)
16725;

Sumując to wszystko wychodzi:
16725x4 + 22x17372 = 449084;

Problem jest taki że w podstawowym teście wychodzi wynik 449033. Ma ktoś jakoś pomysł co jest źle w moim rozumowaniu? Z góry dzięki ;)

Nie wiem co ma do tego C++, to jest czysta matematyka https://pl.wikipedia.org/wiki/Zasada_włączeń_i_wyłączeń
Podszedłbym to tego bardziej klasycznie a nie iteracyjnie -> wszystkie możliwości minus możliwości zabronione.
Wszystkich jest oczywiście 26^4. Gdyby była tylko jedna zabroniona para to mielibyśmy 6*26^2 zabronionych opcji (losujemy brakujące pozycje, 26^2, a potem permutujemy na możliwych 3 pozycjach więc 3! = 6). Tylko że takich par mamy więcej, więc musimy uwzględnić żeby nie zliczać tych samych par wielokrotnie...

To, że wszystkich kombinacji jest 26^4 to jest faktycznie oczywiste, ale nie do końca rozumiem, dlaczego gdyby była jedna para zabroniona, to zabronionych kombinacji będzie 6*26^2. Zadanie to jest zadaniem na programowanie dynamiczne i dlatego zrobiłem to iteracyjnie i próbowałem z jednego kroku dojść do kolejnego. Nie wiem też dlaczego moje rozumowanie jest złe. Mógłby ktoś szerzej opisać?

dlaczego gdyby była jedna para zabroniona, to zabronionych kombinacji będzie 6*26^2

W zasadzie trochę za bardzo uprościłem i takich par jest mniej.
Mamy 4 sloty. 2 zajmie znana nam para, więc pozostają 2 wolne sloty -> 26^2 możliwości dobrania tam wartości. Dla każdej z tych wartości możemy jeszcze zrobić permutacje bo mamy teraz 3 elementy (dwa wylosowane i nasza para) które mogą stanąć na dowolnej pozycji względem siebie, więc 3! ustawień. W zasadzie jest tu mały błąd, bo oczywiście nie wziąlem pod uwgę identycznych możliwości które mogą sie tu pojawić.

Nie mam pojęcia jak to rozwiązać, ale kluczowe są tu dwie rzeczy:

1. n które może być = 30000 (czyli liczba kombinacji 26^30000) - to raczej iteracyjnie się nie da rozwiązać
2. modulo 123456789 które może być ratunkiem przed dużymi liczbami

Da się zrobić iteracyjnie. Wystarczy skorzystać z własności modulo. W tym przykładowym teście nie korzystałem z modulo, bo po co skoro liczba nie przekracza 123456789. We właściwym programie z każdej operacji brałbym dla przykładu:
wynik = (a*b) % MOD;
Problem mam taki, że przeoczyłem jakieś przypadki i wychodzi mi inny wynik niż powinien(pierwszy post).

Sprawdź czy nie jesteś w stanie zdefiniować relacji (funkcji) rekurencyjnej wieloparametrowej opisującej liczbę zabronionych kombinacji, gdzie jednym z parametrów będzie np. Liczba uwzględnionych par albo maksymalna ścieżka zabroniona.

Ps. Temat zdecydowanie należy do działu algorytmy.

Nie potrafię zdefiniować takiej procedury rekurencyjnej.

Można to rozwiązać za pomocą programowania dynamicznego. Niech d[dl][y] oznacza liczbę możliwych haseł o długości dl zaczynających się literą y.

• d[1][a]=1
  -d[dl][y]= suma d[dl-1][y'] dla wszystkich takich y', że para (y,y') nie jest zabroniona.

Czyli ten sam sposób, który opisałem w pierwszym poście. Nie wiem dlaczego ale wynik nie wychodzi poprawny. Zrobiłem taka tabelę zgodnie z testem przykładowym w zadaniu:
https://docs.google.com/spreadsheets/d/1vpVmTP6S60EiPEk_KGBiOA8AfC4ewEnvyexWwR-Me-w/pubhtml

https://docs.google.com/spreadsheets/d/1vpVmTP6S60EiPEk_KGBiOA8AfC4ewEnvyexWwR-Me-w/edit?usp=drivesdk

Algorytm jest dosłownie identyczny co opisałem. Nie zwraca niestety poprawnego wyniku. Możesz sprawdzić czy poprawnie wprowadziłem liczby do tabeli?

Według mnie pierwsze linie tabeli powinny wyglądać tak:
1 1 1 1 1 1 1
25 25 25 26 26 25 26
647 647 647 672 672 646 672
16724 16724 16724 17371 17371 16699 17371

Algorytm nie jest identyczny, bo jednak źle liczysz. Relacja, którą podał Świetny Ogrodnik jest prawdziwa, ale Twoje obliczenia nie wynikają z tej relacji. Intuicyjnie stwierdziłeś, że to jest to samo. A nie jest.

Tabela powinna wygladac tak:

[ 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, ]
[ 25, 25, 25, 26, 26, 25, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, ]
[ 647, 647, 647, 672, 672, 646, 672, 672, 672, 672, 672, 672, 672, 672, 672, 672, 672, 672, 672, 672, 672, 672, 672, 672, 672, 672, ]
[ 16724, 16724, 16724, 17371, 17371, 16699, 17371, 17371, 17371, 17371, 17371, 17371, 17371, 17371, 17371, 17371, 17371, 17371, 17371, 17371, 17371, 17371, 17371, 17371, 17371, 17371, ]

Jeżeli chodzi o samo liczenie z reki to problem zaczyna się już tutaj:

672(ilość wszystkich kombinacji haseł 2-literowych)
(-)
25(ilość kombinacji 2-literowej tylko dla litery 'b')
(=)
647 -> ilość kombinacji haseł 2-literowych jakie mogą nastąpić po literze 'a'.

To samo dla każdej pary opisanej w zadaniu(tzn. tej pierwszej litery z pary).

Otóż nie, dla f wychodzi 646, a nie 647. A to dlatego, że dla g masz 26 kombinacji 2 literowych, nie 25 jak dla b.
Za bardzo uogólniłeś i nie policzyłeś wszystkich liczb poprawnie.

Racja. Zbyt szybko założyłem, że pierwszsze liczby w parze będą mialy te same kombinacje. Niby taki glupi błąd, a jednak stwarza problemy. Dzieki wielkie @nalik i @ŚwietnyOgrodnik. Zadanie raczej wejdzie teraz na 100 pkt. ;)

PS. Rozdalem lajki i akceptacje postu. Dzieki jeszcze raz :P

Nie chce mi przejść na 100 pkt. Prawdopodobnie coś z operacjami modulo mam źle ale nie mogę tego rozgryźć. Może ktoś sprawdzić?
TU BYŁ KOD :)

Źle trzymasz zabronione pary. Jakbyś miał (a, b) i (a,c) to tylko jedną z nich zapamiętałbyś jako zabronioną. Użyj innej reprezentacji, np tablicy dwuwymiarowej.

Poza tym nie widzę byś iterował przez drugą literę z pary.

for i in lengths:
    for x in alphabet:
        combinations[i][x] = sum(combinations[i-1][y] for y in alphabet if not forbidden(x, y))