Thread: [ODD] Testy

https://easyupload.io/ityuv7

Parę dużych testów
Potwierdzam.
Potwierdzam.
Potwierdzam.
Potwierdzam.
Potwierdzam testy Piotra.
potwierdzam obie paczki
Potwierdzam
input: 2137 605
output: 213725353

input: 11 90
output: 213764780
potwierdzam wszystko
Potwierdzam paczkę Piotra

3d7648b2c21f2144658671c5059d9619993329da34b42eb0eb6bec6de860d133 odd.zip
Potwierdzam
Potwierdzam. Proponuję dodatkowe kilka testów:

In: 69 418724788
Out: 213769420

In: 420 648157664
Out: 420692137

In: 2137 210294882
Out: 3141592
Jeszcze jeden zestaw testów - po jednym teście na linijkę. Wszystkie odpowiedzi to 42.

https://gist.github.com/NieDzejkob/be26a76741ddc878f7d1ba74cf326f57
Potwierdzam #24616 , #24626 , #24640 , #24670
Potwierdzam wszystkie testy: te poważne, i te panów śmieszków też.
Potwierdzam testy Anadiego, Piotra i Jakuba
Kuba - szacun za testy :D
Potwierdzam wszystkie testy
potwierdzam wszystkie testy

f2771e52bd18d029a4334fbac14891b94bd16ee09eb5fa8a761b3a3e597e612f a.zip

3d7648b2c21f2144658671c5059d9619993329da34b42eb0eb6bec6de860d133 odd.zip
Potwierdzam wszystkie testy
Kuba, teraz możesz się pochwalić jak generowałeś te testy. Da się coś istotnie szybszego niż n^3+n*mod?
Puszczam kwadratowego DP, ale napisanego w SageMath, gdzie elementami tablicy są wielomiany w m nad Zp. Po obliczeniu odpowiedzi jako wielomian po prostu szukam jego pierwiastków. Wydaje mi się że jest to rzędu n³ log n, w zależności od tego jak Sage mnoży wielomiany. Ale za to mod nie występuje w złożoności (well, technically jest w logu, ale o takiej podstawie że dla 1e9+7 wychodzi 1).
No właśnie zastanawiała mnie ta część "po prostu szukam pierwiastków" i nie spodziewałem się, że da się bez mod w złożoności
Nie interesowałem się tym zbytnio, Sage implementuje wielomian.roots() które jest szybkie (tyle że mod musi być liczbą pierwszą albo musimy znać jego faktoryzację). Być może robi się to jakoś z faktoryzacji wielomianów, ona jest jakoś łatwa obliczeniowo.