Potwierdzam outy Kamila.

Chętnie przyjmę wskazówkę / szkic / rozwiązanie :)

@Adrian, w naszym rozwiązaniu są tylko pamiętane sumy wierszy twojej tabelki (lub kolumn, na to samo wychodzi bo jest symetryczna). Jest t[i] rozwiązań kończących się na sztachecie wypełnionej do max i. Wszystkich jest zatem t[m].

@Adrian
Obiecuję opisać to dokładniej, ale w wolnej chwili (czyli zapewne dopiero za parę dni)

Główna pętla wygląda tak (bez modulo dla przejrzystości):
for (i=1..m) t[i] = t[i-1] + i*(p[m] - p[m-i]) - s, s += p[i];
t to bieżąca tabelka (dla n), a p - poprzednia (dla n-1), obie z wartownikiem 0 na pozycji 0.

Potwierdzam.

Dzięki za odpowiedzi, pytanie jeszcze do Michałów: o jakich m wartościach dokładnie mówicie? Bo ja pisałem m*m, ale dokładnie to jest m*(m+1)/2 (każde poprawne malowanie) wierszy i n kolumn (które faktycznie mogę zredukować do 2). Na przykład dla dwóch segmentów mam wiersze z liczbą możliwych przypadków, które kończą się na 10, 11 i 01, więc pierwsza kolumna to [1 1 1], w drugiej 10 jest sumą 10 i 11 z poprzedniej kolumny, analogicznie 01, natomiast 11 jest sumą wszystkich, więc mamy [2 3 2], trzecia kolumna to [5 7 5] itd. Wynik to suma całej kolumny (liczby odpowiadają zdarzeniom niezależnym).
Pytanie czy mówicie o takich wierszach i to je można jakoś skompresować czy jednak chodzi o coś innego?

Potwierdzam testy Anadiego. Tu są paczki Świstaka z moimi outami: https://easyupload.io/m/dw5nzt

Na medium zgadza mi się tylko jeden test, resztę mam zupełnie inne wyniki. Na big już nawet chwilowo nie patrzyłem. Wrzucam mniejszą paczkę z testami do 15 - https://easyupload.io/f5bo1f, może już tutaj się nie zgodzimy.

Średnie (n=500): https://easyupload.io/us1m6q
Duże (n=500000): https://easyupload.io/3dfy4q
Trochę yolo, głowy nie daję

Kilka całkiem sporych testów
https://easyupload.io/z17b4l

No, tak właśnie zrobiłem jak mój imiennik, tylko w jednym miejscu przekroczyłem zakres inta i tylko 3p :(

Zamiast pamiętać m^2 wartości można przechowywać tylko ich sumę po wierszach (czyli tylko m wartości).

Okazuje się, że na podstawie tylko tych sum można odtworzyć macierz dla następnego poziomu - a następnie policzyć sumy po wierszach następnego poziomu. Można oba kroki połączyć w jeden, dzięki czemu m sum dla jednego poziomu przekształcamy w m sum kolejnego - wykonując m operacji. Całość n razy.

Ja tak jak Jan z tą różnicą że dp2[i][j] = dp[i][m-1-j], więc nie trzeba mieć dwóch tablic, bo liczą to samo.

Dp[i][j] = Na ile sposobów da się pomalować i-ty prefiks płotu, zakładając, że na i-tej sztachecie najwyżej pomalowanym segmentem będzie j.
Dp2 analogicznie, tylko najniżej pomalowanym segmentem będzie j.
Tablica pref to sumy prefiksowe po dp, pref2 po dp2.
Tablica S to sumy prefiksowe po tablicy pref, S2 po pref2
No to dp[i][j] = wszystkie możliwości pomalowania i-1 * j - złe możliwości, czyli wzór mniej więcej taki
dp[i][j] = pref[i-1][m] * j - pref2[i-1][j+1] * j - S[i-1][j-1]
Nie będę tego dokładnie omawiał, można się zastanowić o co dokładnie chodzi :)