English
Temat: [GLA] Testy
https://easyupload.io/mwv7vb
Zamiast liczb x i y na outpucie liczba (x+y) modulo p (p z inputu). Może ktoś potwierdzić?
Zamiast liczb x i y na outpucie liczba (x+y) modulo p (p z inputu). Może ktoś potwierdzić?
Potwierdzam!
Potwierdzam
Jak się to rozwiązuje dla c < a+b-1?
Dało się dogooglać do tego trudniejszego diagramu z omówienia i jest na niego wzorek, więc da się całość w O(ab).
Meh.
Tak, znaliśmy ten wzorek, zresztą dokładny wariant zadania (znaczy kształt tych diagramów) dobraliśmy głównie patrząc dla jakich kształtów brut wypluwa wyniki mające dużo dzielników pierwszych, niemniej nie umieliśmy ani go udowodnić, ani znaleźć źródła dla ogólnego, więc daliśmy w wersji którą umiemy udowodnić
Alternatywne rozwiązanie nie używające diagramów Younga (acz z lekkim wsparciem OEIS)
Klepiemy bruta, z jego pomocą można łatwo zauważyć, że n=a*b - (s+1 choose 2), gdzie s = a+b-1-c. Wrzucenie wyników wprost do OEIS do niczego ciekawego mnie nie doprowadziło.
~~~Case s = 0
Jeżeli zwizualizujemy sobie permutację jako punkty (i, p[i]), a na każdym z nich napiszemy długość najdłuższego ciągu rosnącego zaczynającego się na tej pozycji, to możemy zauważyć że rzutowania tych wartości na osie przypominają coś w stylu wielowymiarowych ciągów catalana, tzn i-te wystąpienie j-tego symbolu musi być przed i-tym wystąpieniem (j-1)-ego symbolu (symbole będę oznaczał jako litery alfabetu). Sugeruje to że wyniki powinny być kwadratami jakiegoś wielowymiarowego uogólnienia liczb catalana, i faktycznie jak spojrzymy na bruta to są kwadratami. Wzięcie pierwiastków i wrzucenie tego w OEIS prowadzi nas do odpowiedniego ciągu oraz wzoru:
https://oeis.org/A060854
T_{n, m} = (m*n)! * 0!..(n-1)! / (m!..(m+n-1)!)
T_{a, b}^2 jest wynikiem w tym przypadku.
~~~Case s > 0
Wyniki bruta nie są w tym przypadku kwadratami, ale ponownie patrząc na rzutowania możemy zgadnąć, że wynik to produkt ilości dwóch następujących obiektów:
O1) czegoś w stylu uogólnienia catalan convolution (https://codeforces.com/blog/entry/87585), gdzie i-tego symbolu (0-indexed) jest s-i mniej, ale udajemy że te brakujące symbole są już na ustalonych pozycjach na początku ciągu
dla np. a=4, b=5, s=2 mamy ustalony początek ciągu AAB, i chcemy odpowiednio dostawić AAA, BBBB, CCCCC, DDDDD tak by warunek z catalana był zachowany. (możliwe że tutaj trzeba odwrócić semantykę a z b etc.)
O2) też jakiś wariant catalana, gdzie usuwamy >pierwszych< s-i kopii i-tego symbolu od końca: dla np. a=4, b=5, s=2 mamy symbole AAAAA,BBBBB,_CCCC,__DDD, przed i-tym B musi być i kopii A, ale przed i-tym C musi być (i+1) kopii B, tak samo dla D.
Jeśli chodzi o weryfikację tych faktów to zadowoliłem się zgodnością z brutem. Te interpretacje są o tyle fajne, że pozwalają na napisanie bruta w złożoności b^a, co pomoże w dalszej części rozwiązania.
~~~
Zauważmy, że T_{n,m} = (n*m choose m,m,m,...,m) / f_n(m)
gdzie f_n(m)=stała*(m+1)^(n-1)..(m+n-1) jest wielomianem od m, stopnia O(n^2), a choose oznacza multinomial coefficient.
Porównując ze zwykłym catalanem, oraz zwykłym catalan convolution możemy zauważyć, że wszystkie te wzorki są postaci
(ilość sposobów na wybranie kolejności elementów bez uważania na ograniczenia) / (jakiś wielomian)
Sugeruje to, że wzór na O1 jest postaci
(n choose b-s,b-s+1,..,b-1,b,b,...,b) / wielomian_{a, s}(b).
Możemy więc próbować interpolować te wielomiany (brut wystarczał do a <= 6). Okazuje się, że istnieją one zarówno dla O1, jak i O2. Rozkładamy je na czynniki i próbujemy znaleźć jakąś prawidłowość. Ze współczynnikiem wiodącym miałem trochę problemów, ale zbiory miejsc zerowych są dość regularne i da się je odgadnąć.
Współczynniki wiodące. Dla s=0 możemy je łatwo wyznaczyć, gdyż w tym przypadku ilość O1 i O2 do T_{n, m}. Okazuje się, że dla s=a-1 współczynnik wiodący jednego z O1/O2 (nie pamiętam już którego) jest taki sam* jak dla s=0, a dla drugiego jest dość podobny (trzeba pomnożyć przez 2^{a choose 2} 0!..(a-1)!).
Wyznaczenie innych współczynników wiodących jest już łatwe - gdy chcemy poznać współczynnik wiodący w wielomianie, znając jego miejsca zerowe, to wystarczy obliczyć wynik dla tylko jednej wartości, a to możemy zrobić dla b=s+1, korzystając z wcześniej obliczonych wartości dla a'=b, b'=a. (zadanie jest symetryczne ze względu na zamianę a z b).
(*wzorki dla tych miejsc zerowych zawierają liczby postaci x/2, więc dla uproszczenia domnażałem je przez jakąś potęgę dwójki by liczby były całkowie, więc możliwe że te współczynnki jednak różnią się o jakąś potęgę dwójki, ale to offtop)
Klepiemy bruta, z jego pomocą można łatwo zauważyć, że n=a*b - (s+1 choose 2), gdzie s = a+b-1-c. Wrzucenie wyników wprost do OEIS do niczego ciekawego mnie nie doprowadziło.
~~~Case s = 0
Jeżeli zwizualizujemy sobie permutację jako punkty (i, p[i]), a na każdym z nich napiszemy długość najdłuższego ciągu rosnącego zaczynającego się na tej pozycji, to możemy zauważyć że rzutowania tych wartości na osie przypominają coś w stylu wielowymiarowych ciągów catalana, tzn i-te wystąpienie j-tego symbolu musi być przed i-tym wystąpieniem (j-1)-ego symbolu (symbole będę oznaczał jako litery alfabetu). Sugeruje to że wyniki powinny być kwadratami jakiegoś wielowymiarowego uogólnienia liczb catalana, i faktycznie jak spojrzymy na bruta to są kwadratami. Wzięcie pierwiastków i wrzucenie tego w OEIS prowadzi nas do odpowiedniego ciągu oraz wzoru:
https://oeis.org/A060854
T_{n, m} = (m*n)! * 0!..(n-1)! / (m!..(m+n-1)!)
T_{a, b}^2 jest wynikiem w tym przypadku.
~~~Case s > 0
Wyniki bruta nie są w tym przypadku kwadratami, ale ponownie patrząc na rzutowania możemy zgadnąć, że wynik to produkt ilości dwóch następujących obiektów:
O1) czegoś w stylu uogólnienia catalan convolution (https://codeforces.com/blog/entry/87585), gdzie i-tego symbolu (0-indexed) jest s-i mniej, ale udajemy że te brakujące symbole są już na ustalonych pozycjach na początku ciągu
dla np. a=4, b=5, s=2 mamy ustalony początek ciągu AAB, i chcemy odpowiednio dostawić AAA, BBBB, CCCCC, DDDDD tak by warunek z catalana był zachowany. (możliwe że tutaj trzeba odwrócić semantykę a z b etc.)
O2) też jakiś wariant catalana, gdzie usuwamy >pierwszych< s-i kopii i-tego symbolu od końca: dla np. a=4, b=5, s=2 mamy symbole AAAAA,BBBBB,_CCCC,__DDD, przed i-tym B musi być i kopii A, ale przed i-tym C musi być (i+1) kopii B, tak samo dla D.
Jeśli chodzi o weryfikację tych faktów to zadowoliłem się zgodnością z brutem. Te interpretacje są o tyle fajne, że pozwalają na napisanie bruta w złożoności b^a, co pomoże w dalszej części rozwiązania.
~~~
Zauważmy, że T_{n,m} = (n*m choose m,m,m,...,m) / f_n(m)
gdzie f_n(m)=stała*(m+1)^(n-1)..(m+n-1) jest wielomianem od m, stopnia O(n^2), a choose oznacza multinomial coefficient.
Porównując ze zwykłym catalanem, oraz zwykłym catalan convolution możemy zauważyć, że wszystkie te wzorki są postaci
(ilość sposobów na wybranie kolejności elementów bez uważania na ograniczenia) / (jakiś wielomian)
Sugeruje to, że wzór na O1 jest postaci
(n choose b-s,b-s+1,..,b-1,b,b,...,b) / wielomian_{a, s}(b).
Możemy więc próbować interpolować te wielomiany (brut wystarczał do a <= 6). Okazuje się, że istnieją one zarówno dla O1, jak i O2. Rozkładamy je na czynniki i próbujemy znaleźć jakąś prawidłowość. Ze współczynnikiem wiodącym miałem trochę problemów, ale zbiory miejsc zerowych są dość regularne i da się je odgadnąć.
Współczynniki wiodące. Dla s=0 możemy je łatwo wyznaczyć, gdyż w tym przypadku ilość O1 i O2 do T_{n, m}. Okazuje się, że dla s=a-1 współczynnik wiodący jednego z O1/O2 (nie pamiętam już którego) jest taki sam* jak dla s=0, a dla drugiego jest dość podobny (trzeba pomnożyć przez 2^{a choose 2} 0!..(a-1)!).
Wyznaczenie innych współczynników wiodących jest już łatwe - gdy chcemy poznać współczynnik wiodący w wielomianie, znając jego miejsca zerowe, to wystarczy obliczyć wynik dla tylko jednej wartości, a to możemy zrobić dla b=s+1, korzystając z wcześniej obliczonych wartości dla a'=b, b'=a. (zadanie jest symetryczne ze względu na zamianę a z b).
(*wzorki dla tych miejsc zerowych zawierają liczby postaci x/2, więc dla uproszczenia domnażałem je przez jakąś potęgę dwójki by liczby były całkowie, więc możliwe że te współczynnki jednak różnią się o jakąś potęgę dwójki, ale to offtop)