Temat: [ODD] Testy

https://easyupload.io/ityuv7

Parę dużych testów

#24616 | Anadi Agrawal | Dodany: 2021-12-06 14:07:32

Potwierdzam.

#24618 | Piotr Kowalewski | Dodany: 2021-12-06 14:32:42

Potwierdzam.

#24621 | Kacper Walentynowicz | Dodany: 2021-12-06 14:47:17

Potwierdzam.

#24622 | Łukasz Pluta | Dodany: 2021-12-06 14:47:29

Potwierdzam.

#24624 | Jacek Salata | Dodany: 2021-12-06 15:01:07

Dużo testów różnej wielkości

https://drive.google.com/file/d/1yF4rr2YV7NpcoDbfYSSB4M07NrEQUP4V/view?usp=sharing

#24626 | Piotr Kowalewski | Dodany: 2021-12-06 15:19:24

Potwierdzam testy Piotra.

#24628 | Jacek Salata | Dodany: 2021-12-06 15:42:10

potwierdzam obie paczki

#24631 | Katzper Michno | Dodany: 2021-12-06 16:09:37

Potwierdzam

#24634 | Krzysztof Potępa | Dodany: 2021-12-06 16:13:12

input: 2137 605
output: 213725353

input: 11 90
output: 213764780

#24640 | Konrad Paluszek | Dodany: 2021-12-06 16:46:17

potwierdzam wszystko

#24649 | Maciej Mejer | Dodany: 2021-12-06 18:07:57

Potwierdzam paczkę Piotra

3d7648b2c21f2144658671c5059d9619993329da34b42eb0eb6bec6de860d133 odd.zip

#24660 | Bartłomiej Czarkowski | Dodany: 2021-12-06 19:10:38

Potwierdzam

#24669 | Michał Stawarz | Dodany: 2021-12-06 20:08:16

Potwierdzam. Proponuję dodatkowe kilka testów:

In: 69 418724788
Out: 213769420

In: 420 648157664
Out: 420692137

In: 2137 210294882
Out: 3141592

#24670 | Maja Kądziołka | Dodany: 2021-12-06 20:21:41

Jeszcze jeden zestaw testów - po jednym teście na linijkę. Wszystkie odpowiedzi to 42.

https://gist.github.com/NieDzejkob/be26a76741ddc878f7d1ba74cf326f57

#24674 | Maja Kądziołka | Dodany: 2021-12-06 20:35:01

Potwierdzam #24616 , #24626 , #24640 , #24670

#24695 | Stanisław Czech | Dodany: 2021-12-06 22:46:25

Potwierdzam wszystkie testy: te poważne, i te panów śmieszków też.

#24709 | Kacper Walentynowicz | Dodany: 2021-12-07 00:04:14

Potwierdzam testy Anadiego, Piotra i Jakuba

#24712 | Marcin Knapik | Dodany: 2021-12-07 00:36:02

Kuba - szacun za testy :D

#24713 | Wojtek Nadara | Dodany: 2021-12-07 00:38:05

Potwierdzam wszystkie testy

#24721 | Szymon Rusiecki | Dodany: 2021-12-07 05:15:04

potwierdzam wszystkie testy

f2771e52bd18d029a4334fbac14891b94bd16ee09eb5fa8a761b3a3e597e612f a.zip

3d7648b2c21f2144658671c5059d9619993329da34b42eb0eb6bec6de860d133 odd.zip

#24735 | Franciszek Witt | Dodany: 2021-12-07 08:43:30

Potwierdzam wszystkie testy

#24818 | Adam Gąsienica-Samek | Dodany: 2021-12-07 19:32:52

Kuba, teraz możesz się pochwalić jak generowałeś te testy. Da się coś istotnie szybszego niż n^3+n*mod?

#24859 | Konrad Paluszek | Dodany: 2021-12-08 00:12:45

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

#24870 | Maja Kądziołka | Dodany: 2021-12-08 04:26:29

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

#24882 | Konrad Paluszek | Dodany: 2021-12-08 09:07:38

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.

#24936 | Maja Kądziołka | Dodany: 2021-12-08 18:31:53