Jak to rozwiązaliście? Rozpisałem ogólne wzorki rekurencyjne dla każdego możliwego typu malowania, np. dla 3 segmentów początkowe 6 możliwości rozwidla się w 2 sztachecie na 3x100, 4x010, 3x001, 5x110, 5x011, 6x111 i kolejne wartości liczą się na podstawie poprzednich, ale to ma w złożoności pamięciowej m*m...

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 :)

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.

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.

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

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?

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.

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

@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].

Okej, chyba rozumiem, czyli to jednak też bazuje na ograniczaniu najwyżej pomalowanego segmentu. Wydaje mi się, że nawet krążyłem nieświadomie przez jakiś czas wokół tego, ale ostatecznie się nie udało. Dzięki za rozjaśnienie. :D

Doszedłem to tego w ten sposób: dla jakiegoś i,j (dół i góra malunku; oznaczony przez x poniżej) trzeba zsumować z poprzedniej tabelki taki pięciokąt (wszystkie 1 oraz x):
111111100
11111110
111x111
111111
11111
1111
000
00
0
a więc całość minus 2 trójkąciki, górny z nich jest sumą 3 wierszy, a dolny sumą 2 kolumn, ale ponieważ wiersze i kolumny można zamienić ze sobą, to wystarczy pamiętać sumę dla wiersza, albo nawet sumę całych takich trójkątów. Jak sobie rozpisałem które trójkąty trzeba dodać i odjąć żeby otrzymać cały wiersz to wyszedł wzór co podałem wcześniej, na początku dodany jest t[i-1] czyli poprzedni wiersz co daje cały trójkąt.

Ups, teraz zobaczyłem, że w treści było m*n<10^7, nie n, m<10^7 🙃