Kombinacje - Metoda: "Dziel i zwyciężaj" - Rekurencja

Pytania o rozwiązania zadań.
Otrzymałeś(aś) rozwiązanie do zamieszczonego zadania? - podziękuj autorowi rozwiązania! Kliknij
Matematyk_Hais
Rozkręcam się
Rozkręcam się
Posty: 50
Rejestracja: 31 mar 2015, 14:49
Podziękowania: 13 razy
Otrzymane podziękowania: 6 razy
Płeć:

Kombinacje - Metoda: "Dziel i zwyciężaj" - Rekurencja

Post autor: Matematyk_Hais » 14 paź 2016, 19:48

Witam,
Kurcze mam zadanie do wykonania, ale nie wiem za bardzo jak się za nie zabrać.
Sprawa wygląda tak, że, mam sobie jakis prostokąt złożony z 0 i 1.
np.:
010
101
i teraz mam określić na ile sposobów można taki prostokąt podzielić, w taki sposób, aby najmniejsza część składała się minimum jednego zera i jednej jedynki.
Rozwiązanie dla takiego prostokąta to:
5 sposobów:
Obrazek
W ogóle ten wynik jest i ma być w modulo 10^9.
Nie mam pojęcia jak się zabrać za te zadanie, o czym warto poczytać. na razie rozpisuję sobie na kartce różne przykłady bo ten prostokąt może mieć wymiary maksymalne 20x20 i rozkminiam próbując znaleźć jakies zależności lub coś zauważyć po rozpisaniu. Ogarnąłem, że chyba ten pierwszy podział można zrobić po wierszach na: liczba_wierszy - 1, tak samo po kolumnach: liczba_kolumn -1.

Matematyk_Hais
Rozkręcam się
Rozkręcam się
Posty: 50
Rejestracja: 31 mar 2015, 14:49
Podziękowania: 13 razy
Otrzymane podziękowania: 6 razy
Płeć:

Post autor: Matematyk_Hais » 14 paź 2016, 21:31

Hej nie wiem czemu ale nie widzę tego tematu w dziale ;/ Zadanie zrobione.