Dwumian Newtona w C++

Question

Witam, dostałem do rozwiązania takie oto zadanko: Głazy. Zauważyłem, że na początku można obliczyć ilość wszystkich sposobów na dotarcie Bajtka do taty. Wartość ta, dla danych wejściowych N oraz M, wyraża się wzorem:

|Ω| = (N + M - 2) po (N - 1), gdzie operacja 'po' oznacza użycie Symbolu Newtona.

Po obliczeniu tej wartości odejmowałbym, za każdym razem gdy wczytam X oraz Y, wartość ( (X + Y - 2) po (X - 1) ) * ( ( (N - X) + (M - Y) ) po (N - X) ), czyli de facto ilość dróg przechodzących przez punkt (X;Y). Wtedy uzyskałbym szukaną wartość.

Niestety nie wiem jak do końca użyć tej zależności w C++. Język ten nie obsługuje tak wielkich liczb jak np. (1e3)! albo co gorsza (1e5)!. Prosiłbym o pomoc w tej kwestii. Dziękuję z góry.

Comments

W O(N*M) możesz napisać 10 linijkowego dp. Można się zastanowić, czy tego dp nie da się jakoś skompresować ze względu na D.

---

W sensie:

dp[i][j] = (dp[i-1][j] + dp[i][j-1] + MOD) % MOD

Oczywiście jak i-1 i j-1 >= 0 jak indeksujemy od 0.

Answer 1

Jeśli masz dwa głazy (x1, y1), (x2, y2) z czego ten pierwszy jest na lewo i do góry od drugiego to tym wzorkiem policzysz scieżkę przechodzącą przez te 2 głazy dwukrotnie. Tu trzeba jakoś skorzystać z tego, że głazów jest co najwyżej 1e3.

Wynik musisz podać modulo 1e9+7 więc nie trzeba bezpośrednio liczyć (1e5)!. Ważna własność:

(a * b) % M = ((a % M) * (b % M)) % M

Answer 2

Rozwiązanie w O(N*D), może przejdzie. Idziemy po wysokościach od 1 do N, nazwijmy tą zmienną i. Trzymamy vector, dp rozmiaru M, min wynik na dojście na daną współrzędna (x,i). Będzie co najwyżej D takich wierszy, gdzie jest jakiś głaz, a N-D bez głazu, te z głazem sobie przesymulujemy normalnie liniowo. A pozostaje nam jak obliczyć takie dziury w sensie:

 

 

Znamy wartości dp w czarnych, i trzeba jakoś szybko wyliczyć jakie będą wartości w czerwonych, H znamy. najlepiej w O(M), bo tak to będzie gorsza złożonność. Pewnie jakaś matma tu wchodzi, nie wiem jak, ale może np iść jakoś mądrze od lewej do prawej po kolumnach.

Comments

Chyba wymyśliłem jak to zrobić. Ciężka matematyka ogranicza się chyba tylko na dodawaniu. Idziemy od lewej do prawej dla wszystkich czarnych. I dp, dla pierwszego z lewej czerwonego, to dp czarnego, nic się nie zmienia. Zdefiniujmy zmienną suma, którą będziemy aktualizować. Najpierw suma = H * dp_pierwsze_czarne, potem dp[2] = suma, aktualizujemy sumę itd.... O(M)