Zabawna gra, jeśli się nudzisz, to gra Diffy . Jest to gra dla jednego gracza, która jest dość prosta i może pochłonąć sporo czasu.

Gra Diffy działa w następujący sposób: Zaczynasz od listy liczb całkowitych nieujemnych, w tym przykładzie użyjemy

3 4 5 8

Następnie bierzesz absolutną różnicę między sąsiednimi liczbami

 (8)  3   4   5   8
    5   1   1   3

Potem powtarzasz. Powtarzaj, dopóki nie uświadomisz sobie, że wszedłeś w pętlę. A potem ogólnie gra zaczyna się od nowa.

3 4 5 8
5 1 1 3
2 4 0 2
0 2 4 2
2 2 2 2
0 0 0 0
0 0 0 0

Często gra nie ma celu, po prostu czekasz czas, wykonując arytmetykę w swojej głowie. Jednak kiedy mam przyjemność grać w tę grę, moim celem jest zawsze próba wybrania okresu i próba zbudowania gry, która zapętla się z tym okresem.

Nie wszystkie gry są okresowe, powyższy przykład nie jest okresowy, na przykład, ponieważ ostatecznie osiąga grę ze wszystkimi zerami, a zatem nigdy nie może wrócić do pozycji początkowej. W rzeczywistości wydaje się, że zdecydowana większość gier nie jest okresowa, co czyni te gry rzadkimi klejnotami.

Biorąc pod uwagę grę, która zapętla się z określonym okresem, trywialne jest stworzenie innej gry, która zapętla się z tym samym okresem, po prostu podwajając sekwencję. Na przykład gra:

1 0 1

Gra dokładnie tak samo jak gra:

1 0 1 1 0 1

W rzeczywistości możemy uznać, że oba są naprawdę nieskończenie powtarzającą się grą:

... 1 0 1 ...

Rozważymy je jako jedną grę ze względu na to wyzwanie.

W podobny sposób pomnożenie całej sekwencji przez stałą również w trywialny sposób zachowa ten okres, więc po raz kolejny policzymy dowolne dwie gry, które różnią się stałym czynnikiem, za tę samą grę.

Nieskończone ciągi znaków ... 1 0 1 ...i ... 0 1 1 ...oczywiście te same ciągi przesunięte o jeden znak. Nie będziemy uważać ich za różne gry, ale kiedy jedna dotrze do drugiej, nie będzie uważana za koniec cyklu przy określaniu okresu gry. Na przykład:

Dwie gry

... 0 0 0 1 0 1 ...  = A
... 0 0 1 1 1 1 ...  = B
... 0 1 0 0 0 1 ...  = A << 4
... 1 1 0 0 1 1 ...  = B << 4
... 0 1 0 1 0 0 ...  = A << 2
... 1 1 1 1 0 0 ...  = B << 2

i

... 0 0 1 0 1 0 ...  = A << 1
... 0 1 1 1 1 0 ...  = B << 1
... 1 0 0 0 1 0 ...  = A << 5
... 1 0 0 1 1 1 ...  = B << 5
... 1 0 1 0 0 0 ...  = A << 3
... 1 1 1 0 0 1 ...  = B << 3

są to gry z okresem 6. Nie dzielą ze sobą żadnego terminu w żadnym punkcie pętli (w przeciwieństwie ... 1 1 0 ...do tych, ... 1 0 1 ...które się do siebie docierają), ale ponieważ są przesuniętymi wersjami, są liczone jako ta sama gra.

Odbicie (lub odwrócenie) nieskończonego łańcucha daje zasadniczo takie samo zachowanie, ale niekoniecznie daje ten sam okres. Zastanów się na przykład

... 0 0 0 1 0 0 1 1 0 1 0 1 1 1 1 ...

i jego odbicie

... 1 1 1 1 0 1 0 1 1 0 0 1 0 0 0 ...

Jeśli uznamy, że następna generacja zostanie wyprodukowana w połowie drogi między postaciami:

... 0 0 0 1 0 0 1 1 0 1 0 1 1 1 1 ...
 ... 0 0 1 1 0 1 0 1 1 1 1 0 0 0 1 ...

... 1 1 1 1 0 1 0 1 1 0 0 1 0 0 0 ...
 ... 0 0 0 1 1 1 1 0 1 0 1 1 0 0 1 ...

wtedy oba zmieniłyby pozycję o 3,5 elementu. Jednak nie uważamy, aby następna generacja była produkowana z tym przesunięciem półelementu, więc jedna zaokrągla w górę do przesunięcia 4-elementowego, co daje okres 15, a druga zaokrągla w dół do przesunięcia 3-elementowego, dając okres z 5.

Z tego powodu uważamy asymetryczny ciąg i jego odbicie za wyraźne, nawet jeśli cykle są w pewnym sensie izomorficzne. Oczywiście, jeśli stanowią część tego samego cyklu, to liczy się tylko jako jeden cykl.

Przy tych ograniczeniach mała matematyka może pokazać, że w rzeczywistości istnieje skończona liczba cykli Diffy'ego w danym okresie skończonym. Co więcej, każdy łańcuch nieskończony z okresem skończonym jest nieskończonym powtórzeniem łańcucha skończonego.

Pamiętaj, że ciągi znaków mogą być większe lub krótsze niż kropki. Na przykład istnieje ciąg o długości 5 z okresem 15 oraz ciąg o długości 15 z okresem 5. Wszystkie ciągi z okresem 19 mają długość 9709.

Zadanie

Biorąc pod uwagę liczbę ntaką, że n jest większy niż 1 za pomocą standardowych metod wprowadzania, określ liczbę różnych cykli Diffy'ego z okresem dokładnie n.

(Wydaje się, że w literaturze 0często nie jest uważana za okresową grę Diffy. Ponieważ jest to szara strefa, o którą nie będę prosić o rozwiązanie n = 1)

To jest golf golfowy , więc celem jest zminimalizowanie liczby bajtów w kodzie źródłowym.

Przypadki testowe

2  ->   0
3  ->   1
4  ->   0
5  ->   1
6  ->   1
7  ->   3
8  ->   0
9  ->   4
10 ->   4
11 ->   3
12 ->   5
13 ->   5
14 ->  24
15 ->  77
16 ->   0
17 -> 259
18 -> 259
19 ->  27
20 -> 272
21 -> 811
22 -> 768
23 ->  91
24 -> 340
25 -> 656

Poradnik

Wszystkie okresowe gry diffy będą zawierały tylko zero i jedną stałą, co oznacza, że ​​każda gra okresowa będzie izomorficzna do niektórych gier diffy składających się tylko z zer i jedynek.

Python 2 , 181 bajtów

n=input()
m=2**n
a=[m]*m
r=lambda i:[i*-~m>>k&m-1 for k in range(n)]
def s(i):
 if a[i]&m:a[i]=i;a[i]=s(min(r(i^i*2)))
 return a[i]
print sum(min(r(i)[1:])>i==s(i)for i in range(m))

Wypróbuj online!

Jak to działa

Reguły, które przekształcają każdy wiersz binarnej gry różnicowej do następnego rzędu, są takie same jak reguły, które przekształcają każdą kolumnę w następną kolumnę. Dlatego wystarczy znaleźć wszystkie odrębne cykle na wykresie wszystkich kanonicznych długości n kolumn, gdzie kolumna jest „kanoniczna”, jeśli jest leksykograficznie mniejsza niż wszystkie swoje obroty (automatycznie wyklucza to kolumny o okresie mniejszym niż n ).

Z kolumnami reprezentowanymi jako liczby binarne 0 ≤ i <2 ⁿ , reguła wysyła i do najmniejszego obrotu i XOR ( i ⋅2). (Jeśli i jest kanoniczny, jego wysoki bit wynosi zero i nie musimy się tutaj martwić.)

Pętlimy więc wszystkie możliwe kolumny i , sprawdzamy kanoniczność, a następnie wielokrotnie stosujemy regułę, aż znajdziemy kolumnę, którą odwiedziliśmy wcześniej, zapamiętując pierwszą taką ponownie odwiedzoną kolumnę. Dokładnie jedna kolumna w każdym cyklu będzie własną pierwszą ponownie odwiedzoną kolumną.