Witam,
Kurcze mam zadanie do wykonania, ale nie wiem za bardzo jak się za nie zabrać.
Sprawaa 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:
W ogóle ten wynik jest i ma być w modulo 10^9
(nie wiem za bardzo o co chodzi z modulo 10^9
, czyli jak otrzymam wynik to mam go przesunąć o 9 miejsc w lewo? Wiem co to modulo, ale nie takie duże czyli: wynik / 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.
No ale przecież sam sobie w temacie odpowiedziałeś -> dziel i zwyciężaj. Widać gołym okiem że problem ma własność optymalnej podstruktury więc wiadomo ze trzeba to liczyć dynamicznie. Tzn (jeśli przespałeś wykłady...) chodzi o to że jeśli wiesz na ile sposobów da się podzielić prostokąt o k-1 wierszach to łatwo na tej podstawie policzyć na ile można podzielić prostkąt o k wierszach. I tak też należy problem moim zadaniem rozwiązać, tzn zrobić macierz M[n][m] i wyliczać ją od najmniejszego fragmentu a na koniec w ostatnim elemencie macierzy będziesz miał finalny wynik.
Modulo to jest po prostu reszta z dzielenia. Pewnie po to żeby ci się wyniki mieściły w zmiennej int. Szczęśliwie dla ciebie jezyki programowania maja operator % który robi właśnie resztę z dzielenia.