Suma odpowiedzi do wszystkich możliwych testów (z t = 1, mod 1e9+7): 447058677

odpalilem wszystkie testy i potwierdzam sume wynikow

Panie, ja nie mam tyle czasu żeby sprawdzać 3^2000000 testów. Mogę spróbować wszystkie testy dla n <= 6 (naginając limit na t): https://pastebin.com/TG3zbKAi

Jest duża szansa że niepoprawnie, ale u mnie wychodzi:

[n=1, 000009 tests] 3706312
[n=2, 000081 tests] 3620916
[n=3, 000729 tests] 6096275
[n=4, 006561 tests] 8102179
[n=5, 059049 tests] 9564056
[n=6, 531441 tests] 2260225

@KM, w jaki sposób dostajesz sume po odpowiedziach do testów n=1 równą 3706312? Dla danego n mamy odpowiedź z góry oszacowaną przez (4n)!, 9*4! < 3706312.

Edit: Spojrzałem na skrypt, nieważne.

Zaprzeczam. Moje wyniki:

[n=1, 000009 tests] 9803929
[n=2, 000081 tests] 3912765
[n=3, 000729 tests] 4993077
[n=4, 006561 tests] 848529
[n=5, 059049 tests] 2822692
[n=6, 531441 tests] 6499953

edit: Nareszcie potwierdzam, dziękuję za te hasze.

Potwierdzam wyniki Krzyśka dla n <= 3, wyżej idk

@Kacper A co dla n > 3? 🥺

Ja potwierdzam hashe krzysztofa, swoja droga polecam zainwestowac w lepszy sprzet, mi sprawdzenie wszystkich 3^2000000 testow zajelo niecale 15min.

Też polecam, ja np. wzorcówkę do tego zadania pisałem po prostu sprawdzając wszystkie (1256^102400-1)/(256-1) możliwe kody mieszczące się w limicie 100kb, policzyło się jakoś w paręnaście minut.

*możliwych kodów, bo ta liczba kończy się na 5 xd

U mnie wychodzi, że suma odpowiedzi dla wszystkich możliwych testów dla n=1000, po dodaniu 25019437 i podniesieniu do potęgi 10^9+6 to 1 (mod 10^9+7)

potwierdzam hashe krzysztofa

Naprawdę doceniam hash Krzysztofa, bardzo pomógł w tym zadaniu.

Nie potwierdzam, nie zaprzeczam.

Skoro już koniec rundy to chciałby ktoś uchylić się wyjaśnić to zadanie? Przesiedziałem nad nim chyba z 15 godzin i na nic nie wpadłem :(

Ja je zrobiłem tak:
Analizując kto ma najlepsze karty, dostajemy np. że jeśli jedna drużyna ma 2 najlepsze karty to zawsze wygrywa. Jeśli się tą analizę kontynuuje, rozważając, które drużyny mają kolejne karty, wychodzi, że aby wygrywający gracz często się zmieniał najlepsze karty muszą należeć do drużyn na zmianę oraz, że gracze mający je muszą siedzieć "po kolei". Do tego wchodzi jakaś okropna przypadkologia żeby wszystkie szczegóły się zgadzały.

Docelowo wszystkie case'y, które trzeba rozpatrzeć, to:
1) jeśli jest jakieś 0 i jakieś 2, to się nie da, bo as na pewno weźmie, a to daje sprzeczne dane na temat tego która z drużyn go ma
2) jeśli gdziekolwiek podane jest, że dla mojej drużyny jest ściśle lepiej jeśli ja wychodzę niż jeśli wychodzi przeciwnik po mojej lewej to też sprzeczność, bo jedyne co to zmienia jeśli wychodzi przeciwnik po mojej lewej zamiast mnie, to że ja podejmuję decyzję na sam koniec, a nie na początek, więc nie mogę na tym stracić
3) jeśli jedna drużyna bierze obie niezależnie kto wychodzi, to to jest równoważne temu, że ta drużyna ma i asa i króla (i nie jest istotne, czy ma je ten sam gracz, czy nie), bo w przeciwnym przypadku, gdyby jedna drużyna miała asa, a druga króla to jeśli pierwszy wychodzi zawodnik, który ma asa, to musi dać wziąć na króla
4) jeśli obie drużyny biorą po jednej niezależnie kto wychodzi, to to jest równoważne temu, że jedna drużyna ma asa, a druga króla i damę (i znowu nie jest istotne, czy król i dama są u tego samego gracza, czy nie), bo w przeciwnym przypadku, albo jedna drużyna ma asa i króla, czyli bierze obie, albo jedna ma asa i damę, a druga króla, to jak pierwszy wychodzi zawodnik, który ma króla to musi dać wziąć i na asa i na damę
5) jeśli żadne z powyższych, czyli albo mamy tylko 1 i 2, albo tylko 0 i 1 i obie liczby występują co najmniej raz, bez straty ogólności zakładamy, że mamy same 1 i 2 to teraz po kolei: asa ma jakiś gracz, który jak wychodzi to jego drużyna weźmie 1 i ma możliwość wzięcia 2 jeśli wychodzi ktoś inny, idziemy od niego przeciwnie do ruchu wskazówek zegara aż znajdziemy kogoś, kto ma przypisane 2 (sprawdzenie warunku 2) gwarantuje nam, że jest to ktoś z przeciwnej drużyny) i on musi mieć króla, idziemy dalej aż znajdziemy jakieś 1 (znowu warunek 2 gwarantuje, że jest to ktoś z tej samej drużyny co ma asa) i on musi mieć damę, jedziemy dalej, znowu jak mamy 2 to ten gracz ma waleta, jak znowu ktoś ma 1 to ma 10 itd. jak zrobimy całe kółko, dojedziemy z powrotem to gracza, który ma asa i przypiszemy X najwyższych kart, to teraz są dwie możliwości
a) dwie najwyższe jakich nie przypisaliśmy należą do którychś graczy (być może obie do tego samego) przeciwnej do tego, który ma najniższą przypisaną, lub
b) najwyższą pozostałą kartę ma gracz przeciwnej drużyny siedzący poza ostatnim łukiem, który rozpatrzyliśmy
i idzie zliczyć ile tego wszystkiego jest jakimiś prostymi dwumianami

Ogólna idea jest, że jak przykładowo mamy asa i króla w przeciwnych drużynach i król jest za asem, to wezmą po jednej lewie, bo gość z królem wie już, czy as został zagrany do pierwszej lewy, czy do drugiej i może zagrać tego króla nie do tej w której jest as, jeśli, w jednej drużynie jest as i dama, a w drugiej król i król jest przed asem i przed damą, to drużyna z AQ bierze dwie lewy, bo do tej lewy, w której jest K zagrają asa, a do tej drugiej damę itd, przykładowo jak jedna drużyna ma A, Q, 10, 8 druga K, J, 9, 7, i wszystkie te karty oprócz 7 są od najmniejszej do największej, to druga drużyna może zagrać K do tej samej lewy, w której jest Q, J do tej samej, w której jest 10, 9 do tej samej, w której jest 8, a jeśli wszystkie te karty są w tej samej lewie, to zagrać 7 do tej drugiej, jedną z tych lew przeciwnicy wezmą asem, a drugą muszą dać nam wziąć, więc drużyny biorą po 1 lewie, podobnie jeśli pierwsza ma A, Q, 10, 8 druga K, J, 9, i wszystkie te karty oprócz 8 są od najmniejszej do największej, to pierwsza drużyna może zagrać A do tej samej lewy, w której jest K, Q do tej samej, w której jest J, 10 do tej samej, w której jest 9, a jeśli wszystkie te karty są w tej samej lewie, to zagrać 8 do tej drugiej i w ten sposób wziąć obie, podobnie, jeśli pierwsza drużyna ma A, Q, 10, 9, a druga K, J i wszystkie są od najmniejszej do największej, to druga drużyna może zagrać 10 do jednej lewy 9 do drugiej, Q do tej samej co J, i A do tej samej co K i w ten sposób wziąć obie