Let \(T_k\) be the Fibonacci tree of order \(k\): \(T_1\) is a single vertex, \(T_2\) is a single edge, and for \(n \ge 3\) the root of \(T_n\) has two child branches that are copies of \(T_{n-1}\) and \(T_{n-2}\). A legal move cuts one edge and deletes the detached subtree. The quantity \(f(k)\) computed by the implementation is the number of first moves on \(T_k\) that leave a position with Grundy value \(0\), and the final answer is required modulo \(10^{18}\).
For any rooted tree \(X\), let \(G(X)\) denote its Sprague-Grundy value. The game on the whole tree splits into independent games on the branches attached to the root, so the total Grundy value is the XOR of the branch contributions.
Now consider a single branch consisting of one edge from the parent to a child subtree \(Y\). If \(G(Y)=g\), then cutting the top edge removes the whole branch and produces contribution \(0\). Any move inside \(Y\) replaces \(Y\) by one of its option values \(u\), so the branch contribution becomes \(1+u\).
Because a subtree of Grundy value \(g\) has options that realize every value \(0,1,\dots,g-1\) and avoid \(g\), the branch has options
$$0,1,2,\dots,g,$$
but not \(g+1\). Therefore the branch itself has Grundy value
$$B(Y)=1+G(Y).$$
Write \(G_n=G(T_n)\). The base trees are immediate:
$$G_1=0,\qquad G_2=1.$$
For \(n \ge 3\), the root of \(T_n\) has branches \(T_{n-1}\) and \(T_{n-2}\). Using the branch rule above and the XOR rule for disjoint impartial subgames, we obtain
$$\boxed{G_n=(1+G_{n-1})\oplus(1+G_{n-2}).}$$
The first few values are
$$G_1=0,\quad G_2=1,\quad G_3=3,\quad G_4=6,\quad G_5=3,\quad G_6=3,\quad G_7=0,\quad G_8=5,\quad G_9=7,\quad G_{10}=14.$$
This precomputation is exactly what the implementation performs before counting any moves.
To count winning moves, define \(C_n(t)\) as the number of ways to make exactly one cut in a branch that is a copy of \(T_n\) so that the surviving rooted branch has Grundy value \(t\). For the recursion it is convenient to extend the state space by the bookkeeping value \(t=-1\): this does not represent a real Grundy number, but the case where the attachment edge itself is cut and the whole branch disappears.
Suppose we are at \(T_n\) with \(n \ge 3\). A cut occurs either inside the \(T_{n-2}\) branch or inside the \(T_{n-1}\) branch.
If the cut is made in the \(T_{n-2}\) branch and that branch ends in bookkeeping state \(u\), then the unchanged \(T_{n-1}\) branch still contributes \(1+G_{n-1}\), while the modified branch contributes \(1+u\). Hence the total Grundy value becomes
$$t=(1+G_{n-1})\oplus(1+u).$$
Solving for \(u\) gives
$$u=((1+G_{n-1})\oplus t)-1.$$
The same argument for the other side yields
$$\boxed{C_n(t)=C_{n-2}\!\left(((1+G_{n-1})\oplus t)-1\right)+C_{n-1}\!\left(((1+G_{n-2})\oplus t)-1\right).}$$
The bookkeeping state is what makes the recurrence clean. There is exactly one way to delete a whole attached branch: cut its attachment edge. Therefore
$$C_n(-1)=1\qquad \text{for every } n\ge 1.$$
Targets below \(-1\) are impossible, so
$$C_n(t)=0\qquad \text{for } t<-1.$$
For the smallest trees:
$$C_1(t)=0\qquad \text{for } t\ge 0,$$
because a single vertex has no edge to cut, and
$$C_2(0)=1,\qquad C_2(t)=0\ \text{for } t\ne 0,$$
because \(T_2\) has exactly one edge, and cutting it leaves a single vertex whose Grundy value is \(0\).
The desired counting function is therefore
$$\boxed{f(k)=C_k(0).}$$
Using \(G_1=0\), \(G_2=1\), \(G_3=3\), \(G_4=6\), compute the needed auxiliary values:
$$C_3(0)=C_1(1)+C_2(0)=0+1=1,$$
$$C_3(1)=C_1(2)+C_2(-1)=0+1=1,$$
$$C_4(3)=C_2(6)+C_3(0)=0+1=1.$$
Now evaluate
$$f(5)=C_5(0)=C_3(6)+C_4(3)=0+1=1.$$
This agrees with the small checkpoint used by the implementation. Another checkpoint is \(f(10)=17\).
The C++, Python, and Java implementations all follow the same plan. First they precompute the sequence \(G_n\) up to the requested \(k\). Then they evaluate the recurrence for \(C_n(t)\) with memoization: for each tree order \(n\), they store only those target values \(t\) that are actually reached. That sparse storage is important because the reachable targets form a small subset of all integers.
Each state is computed once, reduced modulo \(10^{18}\), and reused whenever it reappears. The final value returned is \(C_k(0)\), formatted as the last 18 digits.
Let \(S_n\) be the number of distinct target values \(t\) that are actually visited for tree order \(n\). Precomputing the Grundy sequence costs \(O(k)\) time and \(O(k)\) memory. The memoized recursion computes each reachable pair \((n,t)\) once, so the counting stage costs
$$O\!\left(\sum_{n=1}^{k} S_n\right)$$
time and the same order of memory, up to the constant factors of associative-table lookups. This is dramatically smaller than expanding the full game tree of all possible cuts and resulting positions.
Sei \(T_k\) der Fibonacci-Baum der Ordnung \(k\): \(T_1\) besteht aus einem einzelnen Knoten, \(T_2\) aus genau einer Kante, und für \(n \ge 3\) besitzt die Wurzel von \(T_n\) zwei Äste, die Kopien von \(T_{n-1}\) und \(T_{n-2}\) sind. Ein legaler Zug schneidet eine Kante und entfernt den abgetrennten Teilbaum. Die von der Implementierung berechnete Größe \(f(k)\) ist die Anzahl der ersten Züge auf \(T_k\), die eine Stellung mit Grundy-Wert \(0\) hinterlassen; das Ergebnis wird modulo \(10^{18}\) ausgegeben.
Für jeden verwurzelten Baum \(X\) bezeichne \(G(X)\) seinen Sprague-Grundy-Wert. Das Spiel am gesamten Baum zerfällt an der Wurzel in unabhängige Teilspiele auf den einzelnen Ästen; der Gesamtwert ist daher das XOR der Ast-Beiträge.
Betrachte nun einen einzelnen Ast, der aus einer Kante zur Kindstruktur \(Y\) besteht. Gilt \(G(Y)=g\), dann entfernt das Durchtrennen der oberen Kante den ganzen Ast und liefert den Beitrag \(0\). Ein Zug innerhalb von \(Y\) ersetzt \(Y\) durch einen Optionswert \(u\), und der Ast-Beitrag wird zu \(1+u\).
Da ein Teilspiel mit Grundy-Wert \(g\) Optionen mit allen Werten \(0,1,\dots,g-1\) besitzt, aber nicht \(g\), hat der Ast die Optionen
$$0,1,2,\dots,g,$$
jedoch nicht \(g+1\). Also hat der Ast selbst den Grundy-Wert
$$B(Y)=1+G(Y).$$
Schreibe \(G_n=G(T_n)\). Die Basisfälle sind sofort klar:
$$G_1=0,\qquad G_2=1.$$
Für \(n \ge 3\) hat die Wurzel von \(T_n\) die beiden Äste \(T_{n-1}\) und \(T_{n-2}\). Mit der Ast-Regel von oben und der XOR-Regel für disjunkte unparteiische Teilspiele folgt
$$\boxed{G_n=(1+G_{n-1})\oplus(1+G_{n-2}).}$$
Die ersten Werte sind
$$G_1=0,\quad G_2=1,\quad G_3=3,\quad G_4=6,\quad G_5=3,\quad G_6=3,\quad G_7=0,\quad G_8=5,\quad G_9=7,\quad G_{10}=14.$$
Genau diese Folge wird vor dem eigentlichen Zählen vorab berechnet.
Zum Zählen der Gewinnzüge definieren wir \(C_n(t)\) als die Anzahl der Möglichkeiten, in einem Ast vom Typ \(T_n\) genau eine Kante so zu schneiden, dass der verbleibende verwurzelte Ast den Grundy-Wert \(t\) besitzt. Für die Rekursion wird der Zusatzwert \(t=-1\) eingeführt: Das ist kein echter Grundy-Wert, sondern eine Buchhaltungsmarke für den Fall, dass die Verbindungs-Kante selbst geschnitten wird und der ganze Ast verschwindet.
Für \(n \ge 3\) liegt der Schnitt entweder im Ast \(T_{n-2}\) oder im Ast \(T_{n-1}\).
Geschieht der Schnitt im Ast \(T_{n-2}\) und endet dieser Ast im Buchhaltungszustand \(u\), dann trägt der unveränderte Ast \(T_{n-1}\) weiterhin \(1+G_{n-1}\) bei, der veränderte Ast dagegen \(1+u\). Somit ist der Gesamtwert
$$t=(1+G_{n-1})\oplus(1+u).$$
Nach \(u\) aufgelöst ergibt das
$$u=((1+G_{n-1})\oplus t)-1.$$
Symmetrisch erhält man für beide Seiten zusammen
$$\boxed{C_n(t)=C_{n-2}\!\left(((1+G_{n-1})\oplus t)-1\right)+C_{n-1}\!\left(((1+G_{n-2})\oplus t)-1\right).}$$
Der Zusatzwert macht die Rekursion kompakt. Einen ganzen angehängten Ast kann man genau auf eine Weise löschen: durch Schnitt seiner Verbindungs-Kante. Daher gilt
$$C_n(-1)=1\qquad \text{für alle } n\ge 1.$$
Ziele kleiner als \(-1\) sind unmöglich, also
$$C_n(t)=0\qquad \text{für } t<-1.$$
Für die kleinsten Bäume gilt außerdem
$$C_1(t)=0\qquad \text{für } t\ge 0,$$
denn ein einzelner Knoten enthält keine Kante, und
$$C_2(0)=1,\qquad C_2(t)=0\ \text{für } t\ne 0,$$
weil \(T_2\) genau eine Kante besitzt und ihr Schnitt einen einzelnen Knoten mit Grundy-Wert \(0\) hinterlässt.
Die gesuchte Funktion ist somit
$$\boxed{f(k)=C_k(0).}$$
Mit \(G_1=0\), \(G_2=1\), \(G_3=3\), \(G_4=6\) berechnet man zuerst die nötigen Hilfswerte:
$$C_3(0)=C_1(1)+C_2(0)=0+1=1,$$
$$C_3(1)=C_1(2)+C_2(-1)=0+1=1,$$
$$C_4(3)=C_2(6)+C_3(0)=0+1=1.$$
Dann folgt
$$f(5)=C_5(0)=C_3(6)+C_4(3)=0+1=1.$$
Das stimmt mit dem kleinen Kontrollwert der Implementierung überein. Ein zweiter Kontrollwert ist \(f(10)=17\).
Die C++-, Python- und Java-Implementierungen verwenden dieselbe Struktur. Zuerst wird die Folge \(G_n\) bis zum gewünschten \(k\) vorab berechnet. Danach wird die Rekursion für \(C_n(t)\) mit Memoisierung ausgewertet: Für jede Baumordnung \(n\) werden nur die tatsächlich erreichten Zielwerte \(t\) gespeichert. Diese spärliche Speicherung ist entscheidend, weil die erreichbaren Zielwerte nur einen kleinen Teil aller ganzen Zahlen bilden.
Jeder Zustand wird genau einmal berechnet, sofort modulo \(10^{18}\) reduziert und bei späterem Wiederauftreten wiederverwendet. Am Ende wird \(C_k(0)\) als letzte 18 Ziffern ausgegeben.
Sei \(S_n\) die Anzahl der verschiedenen Zielwerte \(t\), die für Baumordnung \(n\) tatsächlich besucht werden. Die Vorberechnung der Grundy-Folge kostet \(O(k)\) Zeit und \(O(k)\) Speicher. Die memoisierten Zustände \((n,t)\) werden jeweils nur einmal ausgewertet; damit kostet die Zählphase
$$O\!\left(\sum_{n=1}^{k} S_n\right)$$
Zeit und dieselbe Größenordnung an Speicher, bis auf konstante Faktoren der assoziativen Tabellen. Das ist wesentlich kleiner als eine vollständige Expansion aller möglichen Schnitte und Folgestellungen.
\(T_k\), mertebesi \(k\) olan Fibonacci ağacı olsun: \(T_1\) tek bir düğümdür, \(T_2\) tek bir kenardır ve \(n \ge 3\) için \(T_n\)'nin kökü, \(T_{n-1}\) ve \(T_{n-2}\) kopyalarından oluşan iki çocuk dala sahiptir. Yasal hamle, bir kenarı kesip kopan alt ağacı silmektir. Uygulamanın hesapladığı \(f(k)\) değeri, \(T_k\) üzerindeki ilk hamlelerden Grundy değeri \(0\) olan bir konum bırakanların sayısıdır; nihai çıktı \(10^{18}\) modunda istenir.
Herhangi bir köklü ağaç \(X\) için \(G(X)\), onun Sprague-Grundy değeri olsun. Tüm ağaç üzerindeki oyun, köke bağlı dallardaki bağımsız alt oyunların toplamına ayrılır; dolayısıyla toplam Grundy değeri, dal katkılarının XOR'udur.
Şimdi ebeveynden çocuk alt ağaç \(Y\)'ye giden tek bir kenardan oluşan bir dalı düşünelim. Eğer \(G(Y)=g\) ise, üst kenarı kesmek tüm dalı yok eder ve katkı \(0\) olur. \(Y\) içinde yapılan bir hamle ise \(Y\)'yi seçeneklerinden biri olan \(u\) değerine indirger; böylece dal katkısı \(1+u\) olur.
Grundy değeri \(g\) olan bir alt oyunun seçenekleri \(0,1,\dots,g-1\) değerlerinin hepsini içerip \(g\)'yi içermez. Bu yüzden dalın seçenekleri
$$0,1,2,\dots,g,$$
olur ama \(g+1\) olmaz. O halde dalın kendi Grundy değeri
$$B(Y)=1+G(Y).$$
\(G_n=G(T_n)\) yazalım. Başlangıç durumları doğrudan görülür:
$$G_1=0,\qquad G_2=1.$$
\(n \ge 3\) için \(T_n\)'nin kökünde \(T_{n-1}\) ve \(T_{n-2}\) dalları vardır. Yukarıdaki dal kuralı ve ayrık tarafsız oyunlar için XOR kuralı ile
$$\boxed{G_n=(1+G_{n-1})\oplus(1+G_{n-2}).}$$
elde edilir. İlk birkaç değer şunlardır:
$$G_1=0,\quad G_2=1,\quad G_3=3,\quad G_4=6,\quad G_5=3,\quad G_6=3,\quad G_7=0,\quad G_8=5,\quad G_9=7,\quad G_{10}=14.$$
Hamle sayımı başlamadan önce uygulama tam olarak bu diziyi önceden hesaplar.
Kazandıran hamleleri saymak için \(C_n(t)\) fonksiyonunu tanımlayalım: \(T_n\) tipindeki bir dal içinde tam bir kesim yapıldığında, geride kalan köklü dalın Grundy değeri \(t\) ise bunun kaç farklı yoldan gerçekleştiğini saysın. Yinelemeyi temiz yazabilmek için \(t=-1\) yardımcı durumunu da ekliyoruz: bu gerçek bir Grundy değeri değildir, bağlantı kenarının kesilip tüm dalın tamamen yok olması anlamına gelen muhasebe amaçlı bir işarettir.
\(n \ge 3\) iken kesim ya \(T_{n-2}\) dalında ya da \(T_{n-1}\) dalında yapılır.
Eğer kesim \(T_{n-2}\) dalında yapılıp bu dal sonunda \(u\) yardımcı durumuna gelirse, değişmeden kalan \(T_{n-1}\) dalı hâlâ \(1+G_{n-1}\) katkısı yapar; değişen dal ise \(1+u\) katkısı yapar. Bu durumda toplam Grundy değeri
$$t=(1+G_{n-1})\oplus(1+u)$$
olur. Buradan
$$u=((1+G_{n-1})\oplus t)-1$$
bulunur. İki olasılığı birlikte yazınca
$$\boxed{C_n(t)=C_{n-2}\!\left(((1+G_{n-1})\oplus t)-1\right)+C_{n-1}\!\left(((1+G_{n-2})\oplus t)-1\right).}$$
Bu yardımcı durum yinelemeyi sadeleştirir. Tümüyle bağlı bir dalı silmenin tam bir yolu vardır: bağlantı kenarını kesmek. Dolayısıyla
$$C_n(-1)=1\qquad \text{tüm } n\ge 1 \text{ için}.$$
\(-1\)'den küçük hedefler imkansızdır, yani
$$C_n(t)=0\qquad \text{eğer } t<-1.$$
En küçük ağaçlarda ayrıca
$$C_1(t)=0\qquad \text{eğer } t\ge 0,$$
çünkü tek düğümde kesilecek kenar yoktur, ve
$$C_2(0)=1,\qquad C_2(t)=0\ \text{eğer } t\ne 0,$$
çünkü \(T_2\) yalnızca bir kenara sahiptir ve bu kenar kesildiğinde Grundy değeri \(0\) olan tek düğüm kalır.
Aranan fonksiyon böylece
$$\boxed{f(k)=C_k(0).}$$
\(G_1=0\), \(G_2=1\), \(G_3=3\), \(G_4=6\) kullanarak gereken ara değerleri hesaplayalım:
$$C_3(0)=C_1(1)+C_2(0)=0+1=1,$$
$$C_3(1)=C_1(2)+C_2(-1)=0+1=1,$$
$$C_4(3)=C_2(6)+C_3(0)=0+1=1.$$
Sonra
$$f(5)=C_5(0)=C_3(6)+C_4(3)=0+1=1$$
elde edilir. Bu, uygulamanın kullandığı küçük kontrol değeriyle aynıdır. İkinci kontrol noktası \(f(10)=17\)'dir.
C++, Python ve Java uygulamaları aynı planı izler. Önce istenen \(k\)'ye kadar \(G_n\) dizisi hesaplanır. Sonra \(C_n(t)\) yinelemesi memoization ile değerlendirilir: her ağaç boyutu \(n\) için yalnızca gerçekten ulaşılan hedef \(t\) değerleri saklanır. Bu seyrek saklama önemlidir; çünkü erişilebilir hedefler tüm tamsayıların çok küçük bir bölümüdür.
Her durum bir kez hesaplanır, hemen \(10^{18}\) moduna indirilir ve tekrar gerektiğinde yeniden kullanılır. Döndürülen son değer \(C_k(0)\)'dır ve son 18 basamak biçiminde yazdırılır.
\(S_n\), ağaç boyutu \(n\) için gerçekten ziyaret edilen farklı hedef \(t\) sayısı olsun. Grundy dizisinin ön hesabı \(O(k)\) zaman ve \(O(k)\) bellek gerektirir. Memoization ile her erişilebilir \((n,t)\) çifti yalnızca bir kez hesaplandığından sayım aşamasının maliyeti
$$O\!\left(\sum_{n=1}^{k} S_n\right)$$
zaman ve aynı mertebede bellektir; yalnızca ilişkilendirilmiş tablo erişimlerinin sabit çarpanları eklenir. Bu, tüm olası kesimleri ve oluşan konumları açıkça genişletmekten çok daha küçüktür.
Sea \(T_k\) el árbol de Fibonacci de orden \(k\): \(T_1\) es un único vértice, \(T_2\) es una sola arista, y para \(n \ge 3\) la raíz de \(T_n\) tiene dos ramas hijas que son copias de \(T_{n-1}\) y \(T_{n-2}\). Un movimiento legal corta una arista y elimina el subárbol desprendido. La cantidad \(f(k)\) calculada por la implementación es el número de primeros movimientos sobre \(T_k\) que dejan una posición con valor de Grundy \(0\); la respuesta final se toma módulo \(10^{18}\).
Para cualquier árbol enraizado \(X\), denotemos por \(G(X)\) su valor de Sprague-Grundy. El juego sobre el árbol completo se descompone en juegos independientes sobre las ramas que salen de la raíz, de modo que el valor total es el XOR de las contribuciones de cada rama.
Consideremos ahora una sola rama formada por una arista desde el padre hacia un subárbol hijo \(Y\). Si \(G(Y)=g\), entonces cortar la arista superior elimina toda la rama y produce contribución \(0\). En cambio, un movimiento dentro de \(Y\) sustituye \(Y\) por uno de sus valores opción \(u\), así que la contribución de la rama pasa a ser \(1+u\).
Como un subárbol con valor de Grundy \(g\) tiene opciones con todos los valores \(0,1,\dots,g-1\) pero no con \(g\), la rama tiene como opciones
$$0,1,2,\dots,g,$$
pero no \(g+1\). Por lo tanto, el valor de Grundy de la rama es
$$B(Y)=1+G(Y).$$
Escribamos \(G_n=G(T_n)\). Los casos base son inmediatos:
$$G_1=0,\qquad G_2=1.$$
Para \(n \ge 3\), la raíz de \(T_n\) tiene como ramas a \(T_{n-1}\) y \(T_{n-2}\). Aplicando la regla anterior y la suma XOR de subjuegos imparciales disjuntos, obtenemos
$$\boxed{G_n=(1+G_{n-1})\oplus(1+G_{n-2}).}$$
Los primeros valores son
$$G_1=0,\quad G_2=1,\quad G_3=3,\quad G_4=6,\quad G_5=3,\quad G_6=3,\quad G_7=0,\quad G_8=5,\quad G_9=7,\quad G_{10}=14.$$
Esa es exactamente la precomputación que realiza la implementación antes de empezar a contar movimientos.
Para contar movimientos ganadores, definimos \(C_n(t)\) como el número de formas de hacer exactamente un corte en una rama de tipo \(T_n\) de manera que la rama enraizada que sobrevive tenga valor de Grundy \(t\). Para que la recursión sea limpia, se añade también el estado auxiliar \(t=-1\): no es un valor de Grundy real, sino una marca contable que representa cortar la propia arista de unión y hacer desaparecer toda la rama.
Si \(n \ge 3\), el corte ocurre o bien dentro de la rama \(T_{n-2}\) o bien dentro de la rama \(T_{n-1}\).
Si el corte se hace dentro de la rama \(T_{n-2}\) y esa rama termina en el estado auxiliar \(u\), entonces la rama \(T_{n-1}\) no cambia y sigue aportando \(1+G_{n-1}\), mientras que la rama modificada aporta \(1+u\). El valor total pasa a ser
$$t=(1+G_{n-1})\oplus(1+u).$$
Despejando \(u\), se obtiene
$$u=((1+G_{n-1})\oplus t)-1.$$
Repitiendo el mismo razonamiento para la otra rama se llega a
$$\boxed{C_n(t)=C_{n-2}\!\left(((1+G_{n-1})\oplus t)-1\right)+C_{n-1}\!\left(((1+G_{n-2})\oplus t)-1\right).}$$
El estado auxiliar hace que la recurrencia sea compacta. Hay exactamente una forma de borrar por completo una rama colgada: cortar su arista de unión. Por eso
$$C_n(-1)=1\qquad \text{para todo } n\ge 1.$$
Los objetivos menores que \(-1\) son imposibles, así que
$$C_n(t)=0\qquad \text{si } t<-1.$$
Para los árboles más pequeños también se tiene
$$C_1(t)=0\qquad \text{si } t\ge 0,$$
porque un vértice aislado no contiene aristas, y
$$C_2(0)=1,\qquad C_2(t)=0\ \text{si } t\ne 0,$$
porque \(T_2\) tiene exactamente una arista y al cortarla queda un solo vértice de Grundy \(0\).
La función buscada es entonces
$$\boxed{f(k)=C_k(0).}$$
Usando \(G_1=0\), \(G_2=1\), \(G_3=3\) y \(G_4=6\), calculamos primero los valores auxiliares necesarios:
$$C_3(0)=C_1(1)+C_2(0)=0+1=1,$$
$$C_3(1)=C_1(2)+C_2(-1)=0+1=1,$$
$$C_4(3)=C_2(6)+C_3(0)=0+1=1.$$
Luego
$$f(5)=C_5(0)=C_3(6)+C_4(3)=0+1=1.$$
Esto coincide con la comprobación pequeña usada por la implementación. Otra verificación útil es \(f(10)=17\).
Las implementaciones en C++, Python y Java siguen el mismo esquema. Primero precalculan la sucesión \(G_n\) hasta el valor pedido de \(k\). Después evalúan la recurrencia de \(C_n(t)\) con memoización: para cada orden \(n\) del árbol sólo almacenan aquellos valores objetivo \(t\) que realmente aparecen. Ese almacenamiento disperso es esencial porque los objetivos alcanzables forman un subconjunto pequeño de todos los enteros.
Cada estado se calcula una sola vez, se reduce módulo \(10^{18}\) en el acto y se reutiliza siempre que reaparece. El valor final devuelto es \(C_k(0)\), presentado como las últimas 18 cifras.
Sea \(S_n\) el número de valores objetivo distintos \(t\) realmente visitados para el árbol de orden \(n\). La precalculación de la sucesión de Grundy cuesta \(O(k)\) tiempo y \(O(k)\) memoria. Como la recursión memoizada calcula cada par alcanzable \((n,t)\) una sola vez, la fase de conteo cuesta
$$O\!\left(\sum_{n=1}^{k} S_n\right)$$
en tiempo y el mismo orden en memoria, salvo los factores constantes de las tablas asociativas. Esto es muchísimo menor que expandir explícitamente el árbol completo de todos los cortes posibles y todas las posiciones resultantes.
设 \(T_k\) 为第 \(k\) 阶 Fibonacci 树：\(T_1\) 是单个顶点，\(T_2\) 是一条边，而当 \(n \ge 3\) 时，\(T_n\) 的根有两条子分支，分别是 \(T_{n-1}\) 与 \(T_{n-2}\) 的拷贝。一次合法操作是切断一条边，并删除被分离出去的子树。实现中计算的 \(f(k)\) 是：在 \(T_k\) 上所有第一步操作里，有多少步会把局面变成 Grundy 值为 \(0\) 的局面；最后答案按 \(10^{18}\) 取模。
对任意有根树 \(X\)，记 \(G(X)\) 为它的 Sprague-Grundy 值。整棵树上的博弈可以按根的各个子分支拆成若干独立子博弈，因此总 Grundy 值等于各分支贡献的 XOR。
现在看一条单独分支：它由父节点到子树 \(Y\) 的一条边组成。若 \(G(Y)=g\)，那么切掉这条上层边后，整条分支消失，贡献变成 \(0\)。若在 \(Y\) 内部继续走一步，把 \(Y\) 变成某个可达 Grundy 值 \(u\)，那么这条分支对父节点的贡献就变成 \(1+u\)。
因为 Grundy 值为 \(g\) 的子树，其可达值一定覆盖 \(0,1,\dots,g-1\)，但不会出现 \(g\)，所以这条分支的可达贡献正好是
$$0,1,2,\dots,g,$$
而不会出现 \(g+1\)。因此分支自身的 Grundy 值就是
$$B(Y)=1+G(Y).$$
记 \(G_n=G(T_n)\)。最小的两个树直接得到
$$G_1=0,\qquad G_2=1.$$
当 \(n \ge 3\) 时，\(T_n\) 的根拥有两个分支 \(T_{n-1}\) 与 \(T_{n-2}\)。利用上面的分支公式以及独立公平博弈的 XOR 规则，可得
$$\boxed{G_n=(1+G_{n-1})\oplus(1+G_{n-2}).}$$
前几个值为
$$G_1=0,\quad G_2=1,\quad G_3=3,\quad G_4=6,\quad G_5=3,\quad G_6=3,\quad G_7=0,\quad G_8=5,\quad G_9=7,\quad G_{10}=14.$$
实现在真正计数之前，正是先把这串值预处理出来。
为了数出必胜第一步，定义 \(C_n(t)\) 为：对一条类型为 \(T_n\) 的分支，恰好切一次边后，剩下的有根分支 Grundy 值等于 \(t\) 的方案数。递推中还额外引入 \(t=-1\) 这个辅助状态。它不是真正的 Grundy 值，只是一个记账符号，表示直接切掉连接父节点的那条边，于是整个分支完全消失。
当 \(n \ge 3\) 时，唯一的一次切割要么发生在 \(T_{n-2}\) 分支内，要么发生在 \(T_{n-1}\) 分支内。
若切割发生在 \(T_{n-2}\) 分支内，并且该分支切完后对应辅助状态 \(u\)，则未改变的 \(T_{n-1}\) 分支仍然贡献 \(1+G_{n-1}\)，而被修改的那一支贡献 \(1+u\)。于是总 Grundy 值为
$$t=(1+G_{n-1})\oplus(1+u).$$
解出 \(u\) 就得到
$$u=((1+G_{n-1})\oplus t)-1.$$
另一侧完全同理，因此
$$\boxed{C_n(t)=C_{n-2}\!\left(((1+G_{n-1})\oplus t)-1\right)+C_{n-1}\!\left(((1+G_{n-2})\oplus t)-1\right).}$$
辅助状态让递推写法非常整齐。删除一整条挂在父节点下的分支只有一种方式：切掉它的连接边。因此
$$C_n(-1)=1\qquad \text{对所有 } n\ge 1.$$
比 \(-1\) 更小的目标不可能出现，所以
$$C_n(t)=0\qquad \text{当 } t<-1.$$
对最小规模的树，还需要
$$C_1(t)=0\qquad \text{当 } t\ge 0,$$
因为单个顶点根本没有边可切；以及
$$C_2(0)=1,\qquad C_2(t)=0\ \text{当 } t\ne 0,$$
因为 \(T_2\) 只有一条边，切掉之后剩下一个 Grundy 值为 \(0\) 的单顶点。
于是所求函数就是
$$\boxed{f(k)=C_k(0).}$$
利用 \(G_1=0\)、\(G_2=1\)、\(G_3=3\)、\(G_4=6\)，先算出所需的中间量：
$$C_3(0)=C_1(1)+C_2(0)=0+1=1,$$
$$C_3(1)=C_1(2)+C_2(-1)=0+1=1,$$
$$C_4(3)=C_2(6)+C_3(0)=0+1=1.$$
于是
$$f(5)=C_5(0)=C_3(6)+C_4(3)=0+1=1.$$
这与实现里的小规模校验完全一致。另一个校验值是 \(f(10)=17\)。
C++、Python 和 Java 实现使用完全相同的算法框架。第一步先预计算 \(G_n\) 序列直到目标 \(k\)。第二步对 \(C_n(t)\) 做记忆化递归：对每个树阶 \(n\)，只保存实际访问到的目标值 \(t\)。这种稀疏存储非常关键，因为真正会出现的目标值只占整数集合中的很小一部分。
每个状态只计算一次，并立即按 \(10^{18}\) 取模，后面再次遇到时直接复用。最后返回的就是 \(C_k(0)\)，并以最后 18 位数字的形式输出。
设 \(S_n\) 为树阶 \(n\) 时实际访问到的不同目标值 \(t\) 的数量。预计算 Grundy 序列需要 \(O(k)\) 时间和 \(O(k)\) 空间。记忆化递归对每个可达状态对 \((n,t)\) 只求值一次，因此计数阶段的复杂度为
$$O\!\left(\sum_{n=1}^{k} S_n\right)$$
时间，以及同阶的内存消耗，再乘上关联表查找的常数因子。和显式展开所有可能切边与所有后继局面相比，这个规模要小得多。
Пусть \(T_k\) обозначает дерево Фибоначчи порядка \(k\): \(T_1\) состоит из одной вершины, \(T_2\) из одного ребра, а при \(n \ge 3\) корень \(T_n\) имеет две дочерние ветви, являющиеся копиями \(T_{n-1}\) и \(T_{n-2}\). Разрешённый ход состоит в том, чтобы разрезать одно ребро и удалить отделившееся поддерево. Величина \(f(k)\), которую вычисляет реализация, это число первых ходов в \(T_k\), после которых позиция имеет значение Гранди \(0\); итог требуется по модулю \(10^{18}\).
Для любого корневого дерева \(X\) обозначим через \(G(X)\) его значение по теореме Шпрага-Гранди. Игра на всём дереве распадается на независимые игры по ветвям, выходящим из корня, поэтому общее значение равно XOR вкладов отдельных ветвей.
Рассмотрим одну ветвь, состоящую из ребра от родителя к дочернему поддереву \(Y\). Если \(G(Y)=g\), то разрезание верхнего ребра удаляет всю ветвь и даёт вклад \(0\). Если же ход делается внутри \(Y\), то \(Y\) заменяется на одно из своих достижимых значений \(u\), и вклад ветви становится равным \(1+u\).
Так как поддерево со значением Гранди \(g\) имеет ходы ко всем значениям \(0,1,\dots,g-1\), но не к \(g\), то для ветви доступны значения
$$0,1,2,\dots,g,$$
но не \(g+1\). Следовательно, значение Гранди самой ветви равно
$$B(Y)=1+G(Y).$$
Положим \(G_n=G(T_n)\). Базовые случаи очевидны:
$$G_1=0,\qquad G_2=1.$$
Для \(n \ge 3\) у корня \(T_n\) есть ветви \(T_{n-1}\) и \(T_{n-2}\). Из формулы для ветви и XOR-сложения независимых беспристрастных игр получаем
$$\boxed{G_n=(1+G_{n-1})\oplus(1+G_{n-2}).}$$
Первые значения таковы:
$$G_1=0,\quad G_2=1,\quad G_3=3,\quad G_4=6,\quad G_5=3,\quad G_6=3,\quad G_7=0,\quad G_8=5,\quad G_9=7,\quad G_{10}=14.$$
Именно эта последовательность заранее вычисляется перед этапом подсчёта ходов.
Чтобы посчитать выигрышные первые ходы, введём функцию \(C_n(t)\): это число способов сделать ровно один разрез в ветви типа \(T_n\) так, чтобы оставшаяся корневая ветвь имела значение Гранди \(t\). Для удобства рекурсии добавляется вспомогательное состояние \(t=-1\). Это не настоящее значение Гранди, а служебное обозначение случая, когда разрезается само ребро прикрепления, и вся ветвь исчезает.
При \(n \ge 3\) разрез находится либо внутри ветви \(T_{n-2}\), либо внутри ветви \(T_{n-1}\).
Если разрез делается внутри ветви \(T_{n-2}\) и эта ветвь после разреза имеет служебное состояние \(u\), то неизменённая ветвь \(T_{n-1}\) по-прежнему вносит вклад \(1+G_{n-1}\), а изменённая ветвь вносит \(1+u\). Тогда общее значение равно
$$t=(1+G_{n-1})\oplus(1+u).$$
Отсюда
$$u=((1+G_{n-1})\oplus t)-1.$$
Полностью симметрично для другой стороны получаем
$$\boxed{C_n(t)=C_{n-2}\!\left(((1+G_{n-1})\oplus t)-1\right)+C_{n-1}\!\left(((1+G_{n-2})\oplus t)-1\right).}$$
Вспомогательное состояние делает запись очень компактной. Полностью удалить присоединённую ветвь можно ровно одним способом: разрезать ребро, связывающее её с родителем. Поэтому
$$C_n(-1)=1\qquad \text{для всех } n\ge 1.$$
Цели меньше \(-1\) невозможны, значит
$$C_n(t)=0\qquad \text{при } t<-1.$$
Для самых маленьких деревьев дополнительно имеем
$$C_1(t)=0\qquad \text{при } t\ge 0,$$
так как в одной вершине нет ни одного ребра, и
$$C_2(0)=1,\qquad C_2(t)=0\ \text{при } t\ne 0,$$
поскольку \(T_2\) содержит ровно одно ребро, а его разрез оставляет одну вершину со значением Гранди \(0\).
Искомая функция равна
$$\boxed{f(k)=C_k(0).}$$
Используя \(G_1=0\), \(G_2=1\), \(G_3=3\) и \(G_4=6\), сначала найдём необходимые вспомогательные значения:
$$C_3(0)=C_1(1)+C_2(0)=0+1=1,$$
$$C_3(1)=C_1(2)+C_2(-1)=0+1=1,$$
$$C_4(3)=C_2(6)+C_3(0)=0+1=1.$$
Тогда
$$f(5)=C_5(0)=C_3(6)+C_4(3)=0+1=1.$$
Это совпадает с малой контрольной точкой, используемой в реализации. Ещё одна контрольная точка: \(f(10)=17\).
Реализации на C++, Python и Java используют один и тот же план. Сначала они предварительно строят последовательность \(G_n\) до нужного \(k\). Затем рекурсия для \(C_n(t)\) вычисляется с мемоизацией: для каждого порядка дерева \(n\) сохраняются только те значения цели \(t\), которые действительно были достигнуты. Такая разреженная схема важна, потому что достижимые цели образуют лишь небольшое подмножество всех целых чисел.
Каждое состояние вычисляется один раз, сразу приводится по модулю \(10^{18}\) и затем переиспользуется при повторном обращении. Возвращаемое значение равно \(C_k(0)\) и выводится как последние 18 цифр.
Пусть \(S_n\) обозначает число различных целевых значений \(t\), которые реально посещаются для дерева порядка \(n\). Предварительное построение последовательности Гранди требует \(O(k)\) времени и \(O(k)\) памяти. Поскольку мемоизированная рекурсия вычисляет каждый достижимый набор \((n,t)\) только один раз, этап подсчёта имеет сложность
$$O\!\left(\sum_{n=1}^{k} S_n\right)$$
по времени и того же порядка по памяти, не считая постоянных множителей, связанных с ассоциативными таблицами. Это намного меньше, чем явное развертывание всех возможных разрезов и всех получающихся позиций.
لتكن \(T_k\) شجرة فيبوناتشي من الرتبة \(k\): فـ \(T_1\) رأس واحد فقط، و\(T_2\) حافة واحدة، ولـ \(n \ge 3\) يكون لجذر \(T_n\) فرعان ابنان هما نسختان من \(T_{n-1}\) و\(T_{n-2}\). الحركة القانونية هي قطع حافة واحدة ثم حذف الجزء المنفصل من الشجرة. الكمية \(f(k)\) التي تحسبها البرمجيات هي عدد الحركات الأولى على \(T_k\) التي تترك وضعًا ذا قيمة Grundy مساوية لـ \(0\)، وتُؤخذ النتيجة النهائية بترديد \(10^{18}\).
لكل شجرة جذرية \(X\)، نرمز إلى قيمتها وفق مبرهنة Sprague-Grundy بالرمز \(G(X)\). اللعبة على الشجرة كاملة تنفصل عند الجذر إلى ألعاب مستقلة على الفروع الخارجة منه، ولذا تكون القيمة الكلية هي XOR مساهمات هذه الفروع.
انظر الآن إلى فرع واحد مكوَّن من حافة تصل الأب بالجزء الفرعي \(Y\). إذا كانت \(G(Y)=g\)، فإن قطع الحافة العليا يزيل الفرع كله فتكون مساهمته \(0\). أمّا إذا جرت الحركة داخل \(Y\)، فإن \(Y\) يتحول إلى أحد القيم الممكنة \(u\)، وعندها تصبح مساهمة الفرع \(1+u\).
وبما أن الجزء الفرعي ذي قيمة Grundy تساوي \(g\) يملك حركات تصل إلى جميع القيم \(0,1,\dots,g-1\) ولا يصل إلى \(g\)، فإن الفرع يملك القيم الممكنة
$$0,1,2,\dots,g,$$
ولا يملك \(g+1\). لذلك تكون قيمة Grundy للفرع نفسه
$$B(Y)=1+G(Y).$$
لنكتب \(G_n=G(T_n)\). الحالتان الأساسيتان مباشرتان:
$$G_1=0,\qquad G_2=1.$$
وعندما \(n \ge 3\)، يكون لجذر \(T_n\) الفرعان \(T_{n-1}\) و\(T_{n-2}\). باستخدام قاعدة الفرع السابقة وقاعدة XOR لمجموع الألعاب الحيادية المستقلة نحصل على
$$\boxed{G_n=(1+G_{n-1})\oplus(1+G_{n-2}).}$$
وأول القيم هي
$$G_1=0,\quad G_2=1,\quad G_3=3,\quad G_4=6,\quad G_5=3,\quad G_6=3,\quad G_7=0,\quad G_8=5,\quad G_9=7,\quad G_{10}=14.$$
وهذا هو تمامًا الجدول الذي تُعدّه البرمجيات مسبقًا قبل بدء عدّ الحركات.
لحساب الحركات الرابحة، نعرّف \(C_n(t)\) بأنه عدد الطرق لعمل قطع واحد بالضبط داخل فرع من النوع \(T_n\) بحيث تكون قيمة الفرع الجذري الباقي بعد القطع مساوية لـ \(t\). ولأجل كتابة العلاقة التكرارية بشكل نظيف نضيف الحالة المساعدة \(t=-1\). هذه ليست قيمة Grundy حقيقية، بل رمز محاسبي يعني أن حافة الاتصال نفسها قُطعت فاختفى الفرع كله.
إذا كان \(n \ge 3\)، فإن القطع يقع إما داخل الفرع \(T_{n-2}\) أو داخل الفرع \(T_{n-1}\).
فإذا وقع القطع داخل الفرع \(T_{n-2}\) وانتهى ذلك الفرع إلى الحالة المساعدة \(u\)، فإن الفرع غير المتغير \(T_{n-1}\) يظل يساهم بالقيمة \(1+G_{n-1}\)، بينما يساهم الفرع المعدَّل بالقيمة \(1+u\). عندئذ تصبح القيمة الكلية
$$t=(1+G_{n-1})\oplus(1+u).$$
وبحل هذه المعادلة بالنسبة إلى \(u\) نحصل على
$$u=((1+G_{n-1})\oplus t)-1.$$
وبالطريقة نفسها على الجهة الأخرى نحصل على العلاقة
$$\boxed{C_n(t)=C_{n-2}\!\left(((1+G_{n-1})\oplus t)-1\right)+C_{n-1}\!\left(((1+G_{n-2})\oplus t)-1\right).}$$
الحالة المساعدة تجعل العلاقة مضغوطة وواضحة. يوجد أسلوب واحد فقط لإزالة فرع معلّق كامل: قطع حافة اتصاله. لذلك
$$C_n(-1)=1\qquad (n\ge 1).$$
أما الأهداف الأصغر من \(-1\) فمستحيلة، ومن ثم
$$C_n(t)=0\qquad (t<-1).$$
ولأصغر الأشجار لدينا أيضًا
$$C_1(t)=0\qquad (t\ge 0),$$
لأن الرأس المفرد لا يحوي حافة يمكن قطعها، وكذلك
$$C_2(0)=1,\qquad C_2(t)=0 \qquad (t\ne 0),$$
لأن \(T_2\) يحوي حافة واحدة فقط، وقطعها يترك رأسًا واحدًا ذي قيمة Grundy تساوي \(0\).
وبالتالي فإن الدالة المطلوبة هي
$$\boxed{f(k)=C_k(0).}$$
باستخدام \(G_1=0\) و\(G_2=1\) و\(G_3=3\) و\(G_4=6\)، نحسب أولًا القيم المساعدة اللازمة:
$$C_3(0)=C_1(1)+C_2(0)=0+1=1,$$
$$C_3(1)=C_1(2)+C_2(-1)=0+1=1,$$
$$C_4(3)=C_2(6)+C_3(0)=0+1=1.$$
ومن ثم
$$f(5)=C_5(0)=C_3(6)+C_4(3)=0+1=1.$$
وهذا يطابق نقطة الفحص الصغيرة الموجودة في التنفيذ. كما أن قيمة فحص أخرى هي \(f(10)=17\).
تتبع تطبيقات C++ وPython وJava الخطة نفسها. في البداية تُحسب المتتالية \(G_n\) مسبقًا حتى القيمة المطلوبة \(k\). بعد ذلك تُقيَّم علاقة \(C_n(t)\) باستخدام الحفظ التذكري، حيث تُخزَّن لكل رتبة شجرية \(n\) قيم الأهداف \(t\) التي تظهر فعلًا فقط. هذا التخزين المتفرق مهم جدًا لأن القيم القابلة للوصول تشكل مجموعة صغيرة مقارنة بجميع الأعداد الصحيحة.
كل حالة تُحسب مرة واحدة، وتُختزل مباشرةً بترديد \(10^{18}\)، ثم يُعاد استخدامها عند تكرارها. والقيمة النهائية المرجعة هي \(C_k(0)\)، وتُعرض على شكل آخر 18 رقمًا.
لنرمز بـ \(S_n\) إلى عدد قيم الأهداف المختلفة \(t\) التي تُزار فعلًا عند رتبة الشجرة \(n\). حساب متتالية Grundy مسبقًا يكلف \(O(k)\) زمنًا و\(O(k)\) ذاكرة. وبما أن الحفظ التذكري يجعل كل زوج قابل للوصول \((n,t)\) يُحسب مرة واحدة فقط، فإن مرحلة العد تكلف
$$O\!\left(\sum_{n=1}^{k} S_n\right)$$
زمنًا، وبالمقدار نفسه تقريبًا من الذاكرة، مع ثوابت صغيرة مرتبطة بعمليات الوصول إلى الجداول الترابطية. وهذا أصغر بكثير من توسيع جميع القطوع الممكنة وكل الأوضاع الناتجة صراحةً.