English
Forum jest zablokowane. Podczas blokady nie można dodawać ani edytować wiadomości.
Ostatnie posty
To ja mogę wytłumaczyć podzadania.
Jeśli ai <= 100 to suma wszystkich elementów jest mniejsza niż 10^9 + 7
To znaczy, że dowolna suma jest mopadulo jeśli po prostu jest parzysta.
Tutaj możesz już spróbować napisać dynamika T[ i ] [ p / n ] = ile jest możliwości na które można podzielić a[1 .. i] na przedziały które są parzyste, oprócz ostatniego bloku który jest parzysty [p] lub nieparzysty [n].
Jak się przypatrzysz temu rozwiązaniu to zauważysz, że wynikiem zawsze jest potęgą dwójki.
Niech P oznacza liczbę parzystą a N liczbą nieparzystą.
Rozważmy ciąg:
P | P | N P N | N N | P
Jak widzisz pionową kreską oznaczyłem wszystkie prefiksy, które są parzyste.
Ilość możliwości podziałów w takim ciągu wynosi 2^4 (bo 4 to liczba kresek).
Jeśli n <= 3000 to rozwiązanie O(n^2) ma szansę zadziałać.
Robimy algorytm dynamiczny V[i] oznacza na ile możliwości można podzielić ciąg a[1 .. i].
Każdą wartość liczymy w czasie liniowym.
Zaczynamy od ustawienia V[i] = 0
Dla każdego 1 <= j <= i patrzymy czy a[j] + a[j+1] + ... + a[i] jest mopadulu.
Jeśli tak to do V[i] dodajemy V[j-1].
Jeśli ai <= 100 to suma wszystkich elementów jest mniejsza niż 10^9 + 7
To znaczy, że dowolna suma jest mopadulo jeśli po prostu jest parzysta.
Tutaj możesz już spróbować napisać dynamika T[ i ] [ p / n ] = ile jest możliwości na które można podzielić a[1 .. i] na przedziały które są parzyste, oprócz ostatniego bloku który jest parzysty [p] lub nieparzysty [n].
Jak się przypatrzysz temu rozwiązaniu to zauważysz, że wynikiem zawsze jest potęgą dwójki.
Niech P oznacza liczbę parzystą a N liczbą nieparzystą.
Rozważmy ciąg:
P | P | N P N | N N | P
Jak widzisz pionową kreską oznaczyłem wszystkie prefiksy, które są parzyste.
Ilość możliwości podziałów w takim ciągu wynosi 2^4 (bo 4 to liczba kresek).
Jeśli n <= 3000 to rozwiązanie O(n^2) ma szansę zadziałać.
Robimy algorytm dynamiczny V[i] oznacza na ile możliwości można podzielić ciąg a[1 .. i].
Każdą wartość liczymy w czasie liniowym.
Zaczynamy od ustawienia V[i] = 0
Dla każdego 1 <= j <= i patrzymy czy a[j] + a[j+1] + ... + a[i] jest mopadulu.
Jeśli tak to do V[i] dodajemy V[j-1].
Arek, miej litość dla naszych kompów... Nie można by zrobić 300 testów, gdzie q jest jakieś rozsądnie duże?
O(n log n)
Iterujemy się od lewej do prawej licząc cały czas sumy prefixowe modulo M, chcemy dla każdego prefixu policzyć wynik.
Jeżeli widzimy sumę x na [0, i), to przedziały [j, i) są dobre jeśli suma prefixowa [0, j) jest albo tej samej parzystości co x i mniejsza równa niej, albo przeciwnej i ostro większa. To trzymamy na wskaźnikowym drzewie przedziałowym, czy czymś podobnym, indexowanym wartością sumy prefixowej sumy elementów na parzystych i na nieparzystych indexach i po prostu odpytujemy o sumę, by dostać wartość na danym przedziale, i dodajemy w punkcie, żeby zaktualizować strukturę o aktualny prefix.
Iterujemy się od lewej do prawej licząc cały czas sumy prefixowe modulo M, chcemy dla każdego prefixu policzyć wynik.
Jeżeli widzimy sumę x na [0, i), to przedziały [j, i) są dobre jeśli suma prefixowa [0, j) jest albo tej samej parzystości co x i mniejsza równa niej, albo przeciwnej i ostro większa. To trzymamy na wskaźnikowym drzewie przedziałowym, czy czymś podobnym, indexowanym wartością sumy prefixowej sumy elementów na parzystych i na nieparzystych indexach i po prostu odpytujemy o sumę, by dostać wartość na danym przedziale, i dodajemy w punkcie, żeby zaktualizować strukturę o aktualny prefix.
O(n^2):
1) liczymy sumy prefiksowe (modulo)
2) przechodzimy pętlą po każdej wartości o indeksie i, mniejszym od n
3) przechodzimy pętlą po każdej wartości o indeksie j, mniejszym od i
4) jeżeli przedział (j ... i] jest modulo parzysty (co sprawdzamy w czasie stałym, dzięki sumom prefiksowym), to jest już dość dobrze,
bo do podzielenia został nam przedział [0 ... j], dla którego liczbę wszystkich możliwych podziałów mamy już policzoną, więc po prostu dodajemy ją do wyniku dla przedziału [0 ... i].
5) Zapisujemy wynik dla [0 ... i]
6) W momencie, w którym i = n, mamy policzone
1) liczymy sumy prefiksowe (modulo)
2) przechodzimy pętlą po każdej wartości o indeksie i, mniejszym od n
3) przechodzimy pętlą po każdej wartości o indeksie j, mniejszym od i
4) jeżeli przedział (j ... i] jest modulo parzysty (co sprawdzamy w czasie stałym, dzięki sumom prefiksowym), to jest już dość dobrze,
bo do podzielenia został nam przedział [0 ... j], dla którego liczbę wszystkich możliwych podziałów mamy już policzoną, więc po prostu dodajemy ją do wyniku dla przedziału [0 ... i].
5) Zapisujemy wynik dla [0 ... i]
6) W momencie, w którym i = n, mamy policzone
Ja chyba (?) rozwiązałem podzadanie z ai < 300:
Wtedy sumarycznie nigdy nie przekroczymy p. Zatem znajdujemy wszystkie najmniejsze parzyste przedziały np
0 | 1 0 1 | 1 3 | 2 | 6
wynik to 2^ilosc_podzialek % p
Wtedy sumarycznie nigdy nie przekroczymy p. Zatem znajdujemy wszystkie najmniejsze parzyste przedziały np
0 | 1 0 1 | 1 3 | 2 | 6
wynik to 2^ilosc_podzialek % p
+1
Ja prawie miałem n*log^2(n), ale nagle mózg mi zaczął pękać, więc zostałem przy n^2logn :(.
Ja prawie miałem n*log^2(n), ale nagle mózg mi zaczął pękać, więc zostałem przy n^2logn :(.
Hej, byłby ktoś chętny podzielić się jakimiś wskazówkami, a jeszcze lepiej rozwiązaniem?
Kompletnie byłem bez pomysłu, nawet na podzadania.
Kompletnie byłem bez pomysłu, nawet na podzadania.
Pochwali się ktoś?
Potwierdzam wszystko.
Potwierdzam
Potwierdzam
Potwierdzam
https://easyupload.io/dtl1dd
4k małych testów
4k małych testów
Potwierdzam