For \(n=100\), the implementations do not simulate Stone Game Solitaire move by move. They evaluate a closed weighted count modulo \(10^9+7\):
\[ F(n)= (n-1)! \cdot \frac12 \sum_{k=1}^{n-1} \binom{n}{k}\min(k,n-k)\,k^{k-1}(n-k)^{n-k-1}. \]
The real mathematical work is to understand why a complete stone-game configuration can be organized by a distinguished split into groups of sizes \(k\) and \(n-k\), why each side contributes a rooted labeled tree count, and why the remaining factors are exactly \(\min(k,n-k)\), \(1/2\), and \((n-1)!\).
The summand is not an arbitrary product. Each factor has a clean combinatorial meaning, and together they describe the weighted objects counted by the C++, Python, and Java implementations.
The implementations classify the total by a distinguished decomposition of the \(n\) stones into two non-empty parts of sizes \(k\) and \(n-k\). Once \(k\) is fixed, choosing which indices lie on one side contributes the binomial factor
\[ \binom{n}{k}. \]
That is why the whole problem collapses to a single sum over \(k=1,2,\dots,n-1\): the full game history is encoded by the size of one side of the distinguished split and by the structures built on the two sides.
Cayley's formula says that the number of labeled trees on \(m\) vertices is \(m^{m-2}\). If one vertex is additionally distinguished as the point where that side attaches to the rest of the configuration, the tree becomes rooted, so the count is multiplied by \(m\):
\[ m \cdot m^{m-2}=m^{m-1}. \]
Therefore a split of sizes \(k\) and \(n-k\) contributes
\[ k^{k-1}(n-k)^{n-k-1}, \]
which is exactly the number of choices for a rooted labeled tree on each side. In the closed form used by the implementations, the internal history on each side is encoded by those two rooted trees.
The extra weight \(\min(k,n-k)\) shows that the score attached to the distinguished split depends only on the smaller side. When \(k<n/2\), the weight is \(k\); when \(k>n/2\), the complementary choice describes the same split and the same smaller part.
This symmetry is exactly why the formula has the outer factor \(1/2\). The term
\[ \binom{n}{k}\min(k,n-k)\,k^{k-1}(n-k)^{n-k-1} \]
is unchanged under \(k \leftrightarrow n-k\), so summing over all \(k=1,\dots,n-1\) counts complementary splits twice. Dividing by 2 restores the intended unordered count, including the special case \(k=n/2\) when the two sides have equal size.
After the local structure around the distinguished split has been counted, the implementations multiply by \((n-1)!\). Because this factor does not depend on \(k\), it acts as a global ordering multiplier shared by every combinatorial shape counted inside the sum.
That separation is important: all structural information sits inside the symmetric \(k\)-sum, while the universal move-order factor is applied once at the end.
For \(n=4\), the formula becomes
\[ F(4)=3!\cdot \frac12 \left( \binom{4}{1}\cdot 1 \cdot 1^{0}\cdot 3^{2} + \binom{4}{2}\cdot 2 \cdot 2^{1}\cdot 2^{1} + \binom{4}{3}\cdot 1 \cdot 3^{2}\cdot 1^{0} \right). \]
The \(1+3\) and \(3+1\) terms are complementary descriptions of the same split size, so the factor \(1/2\) removes that duplication. Numerically,
\[ F(4)=6\cdot \frac12 (36+48+36)=360. \]
This is one of the exact small cases verified by the integer checks, so it provides a concrete confirmation that the combinatorial interpretation matches the implementation.
Putting everything together, the quantity computed for Stone Game Solitaire is
\[ \boxed{ F(n)= (n-1)! \cdot \frac12 \sum_{k=1}^{n-1} \binom{n}{k}\min(k,n-k)\,k^{k-1}(n-k)^{n-k-1} }. \]
Once this identity is known, the task is no longer a recursive game analysis. It is a fast modular evaluation of a single weighted convolution of rooted-tree counts at \(n=100\).
The C++, Python, and Java implementations precompute factorials and inverse factorials up to \(n\). Since \(10^9+7\) is prime, each inverse is obtained with Fermat's little theorem:
\[ x^{-1}\equiv x^{10^9+5}\pmod{10^9+7}. \]
That makes each binomial coefficient available in constant time through
\[ \binom{n}{k}=\frac{n!}{k!(n-k)!}\pmod{10^9+7}. \]
The main loop runs through \(k=1\) to \(n-1\). For each \(k\), the implementation multiplies the binomial term, the smaller-side weight \(\min(k,n-k)\), and the two rooted-tree factors. The powers \(k^{k-1}\) and \((n-k)^{n-k-1}\) are computed with binary exponentiation, so each term costs \(O(\log n)\) arithmetic operations.
After all terms are summed modulo \(10^9+7\), the result is multiplied by the modular inverse of 2 and finally by \((n-1)!\). The order of operations mirrors the mathematical derivation exactly.
The C++ and Python implementations also recompute small cases in ordinary integer arithmetic before modular reduction. In particular they verify
\[ F(3)=12,\qquad F(4)=360,\qquad F(8)=16785941760. \]
These checks validate the combinatorial formula itself, not just the modular layer.
Precomputing factorials and inverse factorials takes \(O(n)\) time and \(O(n)\) memory. The main sum has \(n-1\) terms, and each term uses two fast exponentiations, so the total running time is \(O(n\log n)\).
For the actual Euler input \(n=100\), this is tiny, but the asymptotic description still matters: the algorithm is efficient because the whole stone-game count has been compressed into one explicit weighted sum.
Für \(n=100\) simulieren die Implementierungen Stone Game Solitaire nicht Zug für Zug. Stattdessen werten sie eine geschlossene, gewichtete Zählung modulo \(10^9+7\) aus:
\[ F(n)= (n-1)! \cdot \frac12 \sum_{k=1}^{n-1} \binom{n}{k}\min(k,n-k)\,k^{k-1}(n-k)^{n-k-1}. \]
Die eigentliche mathematische Arbeit besteht darin zu verstehen, warum sich eine vollständige Steinspiel-Konfiguration nach einer ausgezeichneten Aufteilung in Gruppen der Größen \(k\) und \(n-k\) ordnen lässt, warum jede Seite eine Anzahl verwurzelter markierter Bäume liefert und warum die restlichen Faktoren genau \(\min(k,n-k)\), \(1/2\) und \((n-1)!\) sind.
Der Summand ist kein beliebiges Produkt. Jeder Faktor besitzt eine klare kombinatorische Bedeutung, und zusammen beschreiben sie genau die gewichteten Objekte, die in den C++-, Python- und Java-Implementierungen gezählt werden.
Die Implementierungen klassifizieren die Gesamtsumme nach einer ausgezeichneten Zerlegung der \(n\) Steine in zwei nichtleere Teile der Größen \(k\) und \(n-k\). Ist \(k\) fest, dann liefert die Wahl, welche Indizes auf einer Seite liegen, den Binomialfaktor
\[ \binom{n}{k}. \]
Darum schrumpft das gesamte Problem auf eine einzige Summe über \(k=1,2,\dots,n-1\): Die volle Spielhistorie wird durch die Größe einer Seite der ausgezeichneten Aufteilung und die darauf liegenden Strukturen kodiert.
Nach der Cayley-Formel gibt es \(m^{m-2}\) markierte Bäume auf \(m\) Knoten. Wird zusätzlich ein Knoten als Anknüpfungspunkt an den Rest der Konfiguration ausgezeichnet, so entsteht ein verwurzelter Baum, und die Anzahl wird mit \(m\) multipliziert:
\[ m \cdot m^{m-2}=m^{m-1}. \]
Für eine Aufteilung der Größen \(k\) und \(n-k\) erhält man daher den Faktor
\[ k^{k-1}(n-k)^{n-k-1}, \]
also genau die Anzahl verwurzelter markierter Bäume auf beiden Seiten. In der von den Implementierungen verwendeten geschlossenen Form wird die innere Historie jeder Seite durch diese beiden verwurzelten Bäume kodiert.
Das zusätzliche Gewicht \(\min(k,n-k)\) zeigt, dass die zur ausgezeichneten Aufteilung gehörende Wertung nur von der kleineren Seite abhängt. Für \(k<n/2\) ist das Gewicht einfach \(k\); für \(k>n/2\) beschreibt die komplementäre Wahl dieselbe Aufteilung und dieselbe kleinere Teilmenge.
Genau diese Symmetrie erklärt den äußeren Faktor \(1/2\). Der Ausdruck
\[ \binom{n}{k}\min(k,n-k)\,k^{k-1}(n-k)^{n-k-1} \]
bleibt unter \(k \leftrightarrow n-k\) unverändert. Summiert man also über alle \(k=1,\dots,n-1\), werden komplementäre Aufteilungen doppelt erfasst. Die Division durch 2 stellt die beabsichtigte ungeordnete Zählung wieder her, einschließlich des Spezialfalls \(k=n/2\).
Nachdem die lokale Struktur um die ausgezeichnete Aufteilung gezählt wurde, multiplizieren die Implementierungen mit \((n-1)!\). Da dieser Faktor nicht von \(k\) abhängt, wirkt er als globaler Ordnungsfaktor, der zu jeder innerhalb der Summe gezählten kombinatorischen Form gehört.
Diese Trennung ist wesentlich: Alle Strukturinformationen liegen in der symmetrischen \(k\)-Summe, während der universelle Zugordnungsfaktor erst ganz am Ende angewandt wird.
Für \(n=4\) lautet die Formel
\[ F(4)=3!\cdot \frac12 \left( \binom{4}{1}\cdot 1 \cdot 1^{0}\cdot 3^{2} + \binom{4}{2}\cdot 2 \cdot 2^{1}\cdot 2^{1} + \binom{4}{3}\cdot 1 \cdot 3^{2}\cdot 1^{0} \right). \]
Die Fälle \(1+3\) und \(3+1\) beschreiben komplementär dieselbe Aufteilungsgröße, daher entfernt der Faktor \(1/2\) diese Doppelzählung. Numerisch ergibt sich
\[ F(4)=6\cdot \frac12 (36+48+36)=360. \]
Das ist einer der kleinen exakten Werte, die vor der modularen Rechnung überprüft werden, und damit eine konkrete Bestätigung der mathematischen Deutung.
Damit ergibt sich für Stone Game Solitaire insgesamt
\[ \boxed{ F(n)= (n-1)! \cdot \frac12 \sum_{k=1}^{n-1} \binom{n}{k}\min(k,n-k)\,k^{k-1}(n-k)^{n-k-1} }. \]
Sobald diese Identität feststeht, ist keine rekursive Spielanalyse mehr nötig. Man muss nur noch eine einzige gewichtete Faltung von Baumzahlen effizient modulo \(10^9+7\) auswerten.
Die C++-, Python- und Java-Implementierungen berechnen Fakultäten und inverse Fakultäten bis \(n\) vor. Da \(10^9+7\) prim ist, wird jedes Inverse mit dem kleinen Satz von Fermat gewonnen:
\[ x^{-1}\equiv x^{10^9+5}\pmod{10^9+7}. \]
Damit steht jeder Binomialkoeffizient in konstanter Zeit zur Verfügung:
\[ \binom{n}{k}=\frac{n!}{k!(n-k)!}\pmod{10^9+7}. \]
Die Hauptschleife läuft über \(k=1\) bis \(n-1\). Für jedes \(k\) multipliziert die Implementierung den Binomialterm, das Gewicht der kleineren Seite \(\min(k,n-k)\) und die beiden Baumfaktoren. Die Potenzen \(k^{k-1}\) und \((n-k)^{n-k-1}\) werden mit binärer Exponentiation berechnet, daher kostet jeder Summand \(O(\log n)\) Rechenoperationen.
Nachdem alle Terme modulo \(10^9+7\) aufsummiert wurden, wird mit dem modularen Inversen von 2 und anschließend mit \((n-1)!\) multipliziert. Die Reihenfolge stimmt exakt mit der Herleitung überein.
Die C++- und Python-Implementierungen berechnen kleine Fälle zusätzlich in gewöhnlicher Ganzzahlarithmetik nach, bevor die modulare Reduktion verwendet wird. Geprüft werden insbesondere
\[ F(3)=12,\qquad F(4)=360,\qquad F(8)=16785941760. \]
Diese Tests validieren die kombinatorische Formel selbst und nicht nur die modulare Rechenschicht.
Das Vorberechnen von Fakultäten und inversen Fakultäten benötigt \(O(n)\) Zeit und \(O(n)\) Speicher. Die Hauptsumme besitzt \(n-1\) Terme, und jeder Term verwendet zwei schnelle Potenzierungen, also ergibt sich insgesamt \(O(n\log n)\) Laufzeit.
Für den konkreten Euler-Wert \(n=100\) ist das sehr klein. Die asymptotische Beschreibung bleibt trotzdem wichtig: Die Effizienz kommt daher, dass die gesamte Steinspiel-Zählung auf eine explizite gewichtete Summe komprimiert wurde.
\(n=100\) için uygulamalar Stone Game Solitaire oyununu hamle hamle simüle etmiyor. Bunun yerine \(10^9+7\) modunda şu kapalı ve ağırlıklı sayımı hesaplıyor:
\[ F(n)= (n-1)! \cdot \frac12 \sum_{k=1}^{n-1} \binom{n}{k}\min(k,n-k)\,k^{k-1}(n-k)^{n-k-1}. \]
Asıl matematiksel iş, tam bir taş-oyunu konfigürasyonunun neden \(k\) ve \(n-k\) büyüklüklerinde ayırt edici bir bölünmeye göre düzenlenebildiğini, neden her iki tarafın köklü etiketli ağaç sayımı verdiğini ve kalan çarpanların neden tam olarak \(\min(k,n-k)\), \(1/2\) ve \((n-1)!\) olduğunu anlamaktır.
Toplamdaki terim rastgele bir çarpım değildir. Her faktörün net bir kombinatorik anlamı vardır ve bunların tamamı birlikte C++, Python ve Java uygulamalarının saydığı ağırlıklı nesneleri tanımlar.
Uygulamalar toplam sayımı, \(n\) taşın \(k\) ve \(n-k\) büyüklüklerinde iki boş olmayan kısma ayrıldığı ayırt edici bir ayrışmaya göre sınıflandırır. \(k\) sabitlenince, hangi indislerin bir tarafta olduğunu seçmenin katkısı şu binom katsayısıdır:
\[ \binom{n}{k}. \]
Bu nedenle bütün problem \(k=1,2,\dots,n-1\) üzerindeki tek bir toplama iner. Tüm oyun geçmişi, ayırt edici bölünmenin bir tarafının boyutu ve iki tarafta kurulan yapılarla temsil edilir.
Cayley formülüne göre \(m\) etiketli düğüm üzerindeki ağaç sayısı \(m^{m-2}\)'dir. Eğer ayrıca o tarafın geri kalan yapıya bağlandığı bir düğüm ayırt edilirse ağaç köklenmiş olur ve sayı \(m\) ile çarpılır:
\[ m \cdot m^{m-2}=m^{m-1}. \]
Dolayısıyla boyutları \(k\) ve \(n-k\) olan bir bölünmenin katkısı
\[ k^{k-1}(n-k)^{n-k-1} \]
olur; bu da her iki taraftaki köklü etiketli ağaçların tam sayısıdır. Uygulamaların kullandığı kapalı formda, her tarafın içsel geçmişi bu iki köklü ağaçla kodlanır.
Ek ağırlık olan \(\min(k,n-k)\), ayırt edici bölünmeye bağlı skorun yalnızca daha küçük taraftan geldiğini gösterir. \(k<n/2\) olduğunda bu ağırlık \(k\)'dır; \(k>n/2\) olduğunda ise tamamlayıcı seçim aynı bölünmeyi ve aynı küçük tarafı anlatır.
Bu simetri tam olarak dıştaki \(1/2\) katsayısını açıklar. Şu ifade
\[ \binom{n}{k}\min(k,n-k)\,k^{k-1}(n-k)^{n-k-1} \]
\(k \leftrightarrow n-k\) dönüşümü altında değişmez. Bu nedenle \(k=1,\dots,n-1\) üzerinde toplamak tamamlayıcı bölünmeleri iki kez sayar; 2'ye bölmek, \(k=n/2\) eşit-bölünme durumu dahil olmak üzere doğru sırasız sayımı geri getirir.
Ayırt edici bölünmeye ait yerel yapı sayıldıktan sonra uygulamalar sonucu \((n-1)!\) ile çarpar. Bu çarpan \(k\)'ya bağlı olmadığı için, toplamın içinde sayılan her kombinatorik şekle ortak olan küresel bir sıralama faktörü gibi davranır.
Bu ayrım önemlidir: tüm yapısal bilgi simetrik \(k\)-toplamının içindedir, evrensel hamle-sırası çarpanı ise yalnızca en sonda uygulanır.
\(n=4\) için formül
\[ F(4)=3!\cdot \frac12 \left( \binom{4}{1}\cdot 1 \cdot 1^{0}\cdot 3^{2} + \binom{4}{2}\cdot 2 \cdot 2^{1}\cdot 2^{1} + \binom{4}{3}\cdot 1 \cdot 3^{2}\cdot 1^{0} \right) \]
haline gelir. \(1+3\) ve \(3+1\) terimleri aynı bölünme boyutunun tamamlayıcı anlatımlarıdır; bu yüzden \(1/2\) katsayısı bu çift sayımı kaldırır. Sayısal olarak
\[ F(4)=6\cdot \frac12 (36+48+36)=360. \]
Bu değer, tam sayılı doğrulamalarda kontrol edilen küçük örneklerden biridir; dolayısıyla yorumun kodla gerçekten örtüştüğünü gösteren somut bir kanıttır.
Tüm parçalar birleştirildiğinde Stone Game Solitaire için hesaplanan nicelik
\[ \boxed{ F(n)= (n-1)! \cdot \frac12 \sum_{k=1}^{n-1} \binom{n}{k}\min(k,n-k)\,k^{k-1}(n-k)^{n-k-1} } \]
olur. Bu özdeşlik bilindiğinde mesele artık özyineli bir oyun analizi değildir; yalnızca \(n=100\) için köklü ağaç sayılarının tek bir ağırlıklı toplamını hızlı modüler aritmetikle değerlendirmektir.
C++, Python ve Java uygulamaları \(n\)'e kadar faktöriyelleri ve ters faktöriyelleri önceden hesaplar. \(10^9+7\) asal olduğu için her ters değer Fermat'nın küçük teoremiyle elde edilir:
\[ x^{-1}\equiv x^{10^9+5}\pmod{10^9+7}. \]
Böylece her binom katsayısı sabit zamanda
\[ \binom{n}{k}=\frac{n!}{k!(n-k)!}\pmod{10^9+7} \]
olarak hesaplanabilir.
Ana döngü \(k=1\)'den \(n-1\)'e kadar gider. Her \(k\) için uygulama binom terimini, küçük taraf ağırlığını \(\min(k,n-k)\) ve iki köklü ağaç faktörünü çarpar. \(k^{k-1}\) ile \((n-k)^{n-k-1}\) kuvvetleri ikili üs alma ile hesaplandığından her terim \(O(\log n)\) aritmetik işlem gerektirir.
Tüm terimler \(10^9+7\) modunda toplandıktan sonra sonuç önce 2'nin modüler tersiyle, ardından da \((n-1)!\) ile çarpılır. İşlem sırası matematiksel türetimi bire bir izler.
C++ ve Python uygulamaları ayrıca modüler indirgeme öncesinde küçük durumları normal tam sayı aritmetiğiyle yeniden hesaplar. Özellikle şu değerler doğrulanır:
\[ F(3)=12,\qquad F(4)=360,\qquad F(8)=16785941760. \]
Bu kontroller yalnızca modüler katmanı değil, kombinatorik formülün kendisini sınar.
Faktöriyelleri ve ters faktöriyelleri önceden hesaplamak \(O(n)\) zaman ve \(O(n)\) bellek gerektirir. Ana toplam \(n-1\) terimden oluşur ve her terimde iki hızlı üs alma vardır; dolayısıyla toplam süre \(O(n\log n)\) olur.
Gerçek Euler girdisi \(n=100\) için bu maliyet çok küçüktür. Yine de asimptotik açıklama önemlidir: verimli olmasının nedeni, bütün taş-oyunu sayımının tek bir açık ağırlıklı toplam haline indirgenmiş olmasıdır.
Para \(n=100\), las implementaciones no simulan Stone Game Solitaire jugada por jugada. En su lugar evalúan un conteo cerrado y ponderado módulo \(10^9+7\):
\[ F(n)= (n-1)! \cdot \frac12 \sum_{k=1}^{n-1} \binom{n}{k}\min(k,n-k)\,k^{k-1}(n-k)^{n-k-1}. \]
El trabajo matemático real consiste en entender por qué una configuración completa del juego puede organizarse mediante una partición distinguida en grupos de tamaños \(k\) y \(n-k\), por qué cada lado aporta un conteo de árboles etiquetados con raíz y por qué los factores restantes son exactamente \(\min(k,n-k)\), \(1/2\) y \((n-1)!\).
El sumando no es un producto arbitrario. Cada factor tiene un significado combinatorio claro, y juntos describen los objetos ponderados que cuentan las implementaciones en C++, Python y Java.
Las implementaciones clasifican el total mediante una descomposición distinguida de las \(n\) piedras en dos partes no vacías de tamaños \(k\) y \(n-k\). Una vez fijado \(k\), elegir qué índices quedan en un lado aporta el factor binomial
\[ \binom{n}{k}. \]
Por eso todo el problema se reduce a una sola suma sobre \(k=1,2,\dots,n-1\): toda la historia del juego queda codificada por el tamaño de uno de los lados de esa partición distinguida y por las estructuras construidas en ambos lados.
La fórmula de Cayley dice que el número de árboles etiquetados sobre \(m\) vértices es \(m^{m-2}\). Si además se distingue un vértice como punto de conexión con el resto de la configuración, el árbol queda enraizado y el conteo se multiplica por \(m\):
\[ m \cdot m^{m-2}=m^{m-1}. \]
Por tanto, una partición de tamaños \(k\) y \(n-k\) aporta
\[ k^{k-1}(n-k)^{n-k-1}, \]
que es exactamente el número de elecciones de un árbol etiquetado con raíz en cada lado. En la forma cerrada usada por las implementaciones, la historia interna de cada lado queda codificada por esos dos árboles enraizados.
El peso extra \(\min(k,n-k)\) muestra que la puntuación asociada a la partición distinguida depende solo del lado menor. Cuando \(k<n/2\), ese peso es \(k\); cuando \(k>n/2\), la elección complementaria describe la misma partición y el mismo lado pequeño.
Esa simetría explica exactamente el factor exterior \(1/2\). El término
\[ \binom{n}{k}\min(k,n-k)\,k^{k-1}(n-k)^{n-k-1} \]
no cambia bajo \(k \leftrightarrow n-k\). Por tanto, sumar sobre todos los \(k=1,\dots,n-1\) cuenta dos veces las particiones complementarias. Dividir entre 2 restaura el conteo no ordenado correcto, incluido el caso especial \(k=n/2\).
Después de contar la estructura local alrededor de la partición distinguida, las implementaciones multiplican por \((n-1)!\). Como este factor no depende de \(k\), actúa como un multiplicador global de ordenación compartido por toda forma combinatoria contada dentro de la suma.
Esa separación es importante: toda la información estructural está dentro de la suma simétrica en \(k\), mientras que el factor universal de orden de jugadas se aplica una sola vez al final.
Para \(n=4\), la fórmula se convierte en
\[ F(4)=3!\cdot \frac12 \left( \binom{4}{1}\cdot 1 \cdot 1^{0}\cdot 3^{2} + \binom{4}{2}\cdot 2 \cdot 2^{1}\cdot 2^{1} + \binom{4}{3}\cdot 1 \cdot 3^{2}\cdot 1^{0} \right). \]
Los casos \(1+3\) y \(3+1\) son descripciones complementarias del mismo tamaño de partición, así que el factor \(1/2\) elimina esa duplicación. Numéricamente,
\[ F(4)=6\cdot \frac12 (36+48+36)=360. \]
Este es uno de los casos pequeños verificados con aritmética exacta, por lo que sirve como confirmación concreta de que la interpretación combinatoria coincide con la implementación.
Reuniendo todas las piezas, la cantidad calculada para Stone Game Solitaire es
\[ \boxed{ F(n)= (n-1)! \cdot \frac12 \sum_{k=1}^{n-1} \binom{n}{k}\min(k,n-k)\,k^{k-1}(n-k)^{n-k-1} }. \]
Una vez conocida esta identidad, el problema deja de ser un análisis recursivo del juego. Pasa a ser una evaluación modular rápida de una sola convolución ponderada de conteos de árboles enraizados para \(n=100\).
Las implementaciones en C++, Python y Java precomputan factoriales y factoriales inversos hasta \(n\). Como \(10^9+7\) es primo, cada inverso se obtiene mediante el pequeño teorema de Fermat:
\[ x^{-1}\equiv x^{10^9+5}\pmod{10^9+7}. \]
Así, cada coeficiente binomial queda disponible en tiempo constante mediante
\[ \binom{n}{k}=\frac{n!}{k!(n-k)!}\pmod{10^9+7}. \]
El bucle principal recorre \(k=1\) hasta \(n-1\). Para cada \(k\), la implementación multiplica el término binomial, el peso del lado menor \(\min(k,n-k)\) y los dos factores de árboles enraizados. Las potencias \(k^{k-1}\) y \((n-k)^{n-k-1}\) se calculan con exponenciación binaria, por lo que cada sumando cuesta \(O(\log n)\) operaciones aritméticas.
Después de sumar todos los términos módulo \(10^9+7\), el resultado se multiplica por el inverso modular de 2 y finalmente por \((n-1)!\). El orden de esas operaciones refleja exactamente la derivación matemática.
Las versiones de C++ y Python también recalculan casos pequeños con aritmética entera ordinaria antes de aplicar la reducción modular. En particular verifican
\[ F(3)=12,\qquad F(4)=360,\qquad F(8)=16785941760. \]
Estas comprobaciones validan la propia fórmula combinatoria, no solo la capa modular.
Precomputar factoriales y factoriales inversos requiere \(O(n)\) tiempo y \(O(n)\) memoria. La suma principal tiene \(n-1\) términos, y cada uno usa dos exponenciaciones rápidas, por lo que el tiempo total es \(O(n\log n)\).
Para la entrada real de Euler, \(n=100\), el coste es pequeño. Aun así, la descripción asintótica importa: la eficiencia viene de haber comprimido todo el conteo del juego en una sola suma ponderada explícita.
对于 \(n=100\)，这些实现并不是逐步模拟 Stone Game Solitaire 的全部操作，而是直接在模 \(10^9+7\) 下计算一个封闭的加权计数：
\[ F(n)= (n-1)! \cdot \frac12 \sum_{k=1}^{n-1} \binom{n}{k}\min(k,n-k)\,k^{k-1}(n-k)^{n-k-1}. \]
真正需要解释的是：为什么一个完整的石子局面可以按一个被选中的二分拆来组织，其中两边的大小分别是 \(k\) 和 \(n-k\)；为什么每一边都会出现一个带根标号树的计数；以及为什么剩下的因子恰好是 \(\min(k,n-k)\)、\(1/2\) 和 \((n-1)!\)。
求和式里的各个因子并不是随意拼出来的。每一项都有明确的组合意义，而它们合在一起，正好描述了 C++、Python 和 Java 实现真正计算的加权对象。
这些实现把总数按照一种被选中的划分来分类：把 \(n\) 个石子分成两个非空部分，大小分别为 \(k\) 和 \(n-k\)。在固定 \(k\) 之后，先决定哪一些编号落在其中一边，这一步给出二项式因子
\[ \binom{n}{k}. \]
因此，整个问题被压缩成了对 \(k=1,2,\dots,n-1\) 的单重求和。复杂的完整对局不再逐步展开，而是通过这个被选中的分拆大小以及两边各自承载的结构来编码。
Cayley 公式告诉我们，在 \(m\) 个标号顶点上，标号树的个数是 \(m^{m-2}\)。如果再额外指定一个顶点，作为这一侧与其余部分连接的入口，那么这棵树就变成了一棵带根树，计数会再乘上 \(m\)：
\[ m \cdot m^{m-2}=m^{m-1}. \]
所以，当分拆两边的大小分别是 \(k\) 和 \(n-k\) 时，就会得到
\[ k^{k-1}(n-k)^{n-k-1}, \]
这正是两侧各自选择一棵带根标号树的总方式数。换句话说，在实现所使用的封闭形式里，分拆之后每一侧的内部演化都被编码成一棵带根树。
额外的权重 \(\min(k,n-k)\) 说明，与这个被选中的分拆相关的计分只依赖于较小的那一侧。当 \(k<n/2\) 时，这个权重就是 \(k\)；当 \(k>n/2\) 时，互补的选择描述的是同一个分拆，因此较小部分并没有变化。
这正好解释了外面的 \(1/2\) 因子。表达式
\[ \binom{n}{k}\min(k,n-k)\,k^{k-1}(n-k)^{n-k-1} \]
在 \(k \leftrightarrow n-k\) 的替换下保持不变。所以如果对所有 \(k=1,\dots,n-1\) 直接求和，互补分拆会被计算两次。再除以 2 之后，才恢复成真正想要的无序计数；当 \(k=n/2\) 时，两边等大，这个因子同样自然地处理了该情况。
在与分拆相关的局部结构都统计完之后，这些实现会再统一乘上 \((n-1)!\)。因为这个因子完全不依赖于 \(k\)，所以它可以理解为对每一种局部组合形状都共同适用的全局排序因子。
这种分离非常重要：所有结构信息都放在对 \(k\) 的对称求和里，而通用的操作顺序因子只在最后统一乘一次。
当 \(n=4\) 时，公式变成
\[ F(4)=3!\cdot \frac12 \left( \binom{4}{1}\cdot 1 \cdot 1^{0}\cdot 3^{2} + \binom{4}{2}\cdot 2 \cdot 2^{1}\cdot 2^{1} + \binom{4}{3}\cdot 1 \cdot 3^{2}\cdot 1^{0} \right). \]
其中 \(1+3\) 和 \(3+1\) 是同一种分拆规模的互补写法，因此外面的 \(1/2\) 正好去掉这部分重复。数值上有
\[ F(4)=6\cdot \frac12 (36+48+36)=360. \]
这个值正是小规模精确校验里验证过的结果之一，所以它提供了一个非常具体的检验点，说明上面的组合解释与代码实现是一致的。
把所有部分合在一起，Stone Game Solitaire 最终计算的量就是
\[ \boxed{ F(n)= (n-1)! \cdot \frac12 \sum_{k=1}^{n-1} \binom{n}{k}\min(k,n-k)\,k^{k-1}(n-k)^{n-k-1} }. \]
一旦这个恒等式已经建立，问题就不再是递归地分析游戏过程，而只是对 \(n=100\) 快速求出一个带根树计数的加权卷积。
C++、Python 和 Java 实现都会先预处理到 \(n\) 为止的阶乘和逆阶乘。因为模数 \(10^9+7\) 是素数，所以逆元可以通过费马小定理得到：
\[ x^{-1}\equiv x^{10^9+5}\pmod{10^9+7}. \]
这样每个二项式系数都能在常数时间内写成
\[ \binom{n}{k}=\frac{n!}{k!(n-k)!}\pmod{10^9+7}. \]
主循环遍历 \(k=1\) 到 \(n-1\)。对于每个 \(k\)，实现把二项式因子、较小一侧的权重 \(\min(k,n-k)\) 以及两边的带根树因子相乘。幂 \(k^{k-1}\) 和 \((n-k)^{n-k-1}\) 通过二进制快速幂得到，因此每一项的代价是 \(O(\log n)\) 次模运算。
所有项在模 \(10^9+7\) 下累加后，结果先乘上 2 的模逆元，再乘上 \((n-1)!\)。这与数学推导中的操作顺序完全一致。
C++ 和 Python 版本还会在取模之前，用普通整数运算重新计算一些小规模结果。它们验证了
\[ F(3)=12,\qquad F(4)=360,\qquad F(8)=16785941760. \]
这些校验验证的是组合公式本身，而不仅仅是模运算实现是否正确。
预处理阶乘和逆阶乘需要 \(O(n)\) 时间和 \(O(n)\) 空间。主求和共有 \(n-1\) 项，而每一项都要做两次快速幂，因此总时间复杂度是 \(O(n\log n)\)。
对于实际的 Euler 输入 \(n=100\)，这个开销非常小。但渐近复杂度仍然值得说明，因为算法快的根本原因，是把整个石子游戏的计数压缩成了一个显式的加权求和。
Для \(n=100\) реализации не моделируют Stone Game Solitaire ход за ходом. Вместо этого они вычисляют замкнутую взвешенную сумму по модулю \(10^9+7\):
\[ F(n)= (n-1)! \cdot \frac12 \sum_{k=1}^{n-1} \binom{n}{k}\min(k,n-k)\,k^{k-1}(n-k)^{n-k-1}. \]
Главная математическая задача состоит в том, чтобы понять, почему полную конфигурацию игры можно организовать через выделенное разбиение на группы размеров \(k\) и \(n-k\), почему каждая сторона дает число корневых помеченных деревьев и почему оставшиеся множители равны именно \(\min(k,n-k)\), \(1/2\) и \((n-1)!\).
Слагаемое в сумме не является случайным произведением. У каждого множителя есть четкий комбинаторный смысл, и вместе они описывают те взвешенные объекты, которые считают реализации на C++, Python и Java.
Реализации классифицируют общий счет по выделенному разбиению \(n\) камней на две непустые части размеров \(k\) и \(n-k\). Когда \(k\) фиксирован, выбор того, какие индексы попадут в одну из частей, дает биномиальный множитель
\[ \binom{n}{k}. \]
Именно поэтому вся задача сжимается до одной суммы по \(k=1,2,\dots,n-1\): полная история игры кодируется размером одной стороны выделенного разбиения и структурами, построенными на обеих сторонах.
Формула Кэли утверждает, что число помеченных деревьев на \(m\) вершинах равно \(m^{m-2}\). Если дополнительно выделить вершину, через которую эта часть присоединяется к остальной конфигурации, дерево становится корневым, и счет умножается на \(m\):
\[ m \cdot m^{m-2}=m^{m-1}. \]
Следовательно, разбиение размеров \(k\) и \(n-k\) дает вклад
\[ k^{k-1}(n-k)^{n-k-1}, \]
то есть ровно число способов выбрать по одному корневому помеченному дереву на каждой стороне. В закрытой формуле, используемой реализациями, внутренняя история каждой части кодируется этими двумя корневыми деревьями.
Дополнительный вес \(\min(k,n-k)\) показывает, что вклад выделенного разбиения зависит только от меньшей части. Если \(k<n/2\), этот вес равен \(k\); если \(k>n/2\), то дополнительный выбор описывает то же самое разбиение и ту же меньшую сторону.
Именно эта симметрия объясняет внешний множитель \(1/2\). Выражение
\[ \binom{n}{k}\min(k,n-k)\,k^{k-1}(n-k)^{n-k-1} \]
не меняется при замене \(k \leftrightarrow n-k\). Поэтому суммирование по всем \(k=1,\dots,n-1\) дважды учитывает комплементарные разбиения. Деление на 2 возвращает правильный неупорядоченный счет, включая особый случай \(k=n/2\).
После того как локальная структура вокруг выделенного разбиения подсчитана, реализации умножают результат на \((n-1)!\). Поскольку этот множитель не зависит от \(k\), он выступает как глобальный фактор упорядочения, общий для каждой комбинаторной формы внутри суммы.
Это разделение принципиально: вся структурная информация находится внутри симметрической суммы по \(k\), а универсальный фактор порядка ходов применяется только в самом конце.
При \(n=4\) формула принимает вид
\[ F(4)=3!\cdot \frac12 \left( \binom{4}{1}\cdot 1 \cdot 1^{0}\cdot 3^{2} + \binom{4}{2}\cdot 2 \cdot 2^{1}\cdot 2^{1} + \binom{4}{3}\cdot 1 \cdot 3^{2}\cdot 1^{0} \right). \]
Случаи \(1+3\) и \(3+1\) являются комплементарными описаниями одного и того же размера разбиения, поэтому множитель \(1/2\) устраняет эту двойную запись. Численно получаем
\[ F(4)=6\cdot \frac12 (36+48+36)=360. \]
Это одно из малых точных значений, используемых в проверках, поэтому пример служит конкретным подтверждением того, что комбинаторная интерпретация совпадает с кодом.
В итоге для Stone Game Solitaire вычисляется величина
\[ \boxed{ F(n)= (n-1)! \cdot \frac12 \sum_{k=1}^{n-1} \binom{n}{k}\min(k,n-k)\,k^{k-1}(n-k)^{n-k-1} }. \]
Когда это тождество установлено, задача перестает быть рекурсивным анализом игры и превращается в быструю модульную оценку одной взвешенной свертки счетов корневых деревьев при \(n=100\).
Реализации на C++, Python и Java заранее вычисляют факториалы и обратные факториалы до \(n\). Так как \(10^9+7\) является простым числом, обратные элементы находятся по малой теореме Ферма:
\[ x^{-1}\equiv x^{10^9+5}\pmod{10^9+7}. \]
После этого любой биномиальный коэффициент доступен за константное время:
\[ \binom{n}{k}=\frac{n!}{k!(n-k)!}\pmod{10^9+7}. \]
Основной цикл проходит по \(k=1,\dots,n-1\). Для каждого \(k\) реализация перемножает биномиальный множитель, вес меньшей стороны \(\min(k,n-k)\) и два фактора корневых деревьев. Степени \(k^{k-1}\) и \((n-k)^{n-k-1}\) вычисляются бинарным возведением в степень, поэтому каждое слагаемое требует \(O(\log n)\) арифметических операций.
После суммирования всех членов по модулю \(10^9+7\) результат умножается на модульный обратный к 2, а затем на \((n-1)!\). Этот порядок полностью повторяет математический вывод.
Версии на C++ и Python дополнительно пересчитывают малые случаи в обычной целочисленной арифметике до применения модуля. В частности, проверяются значения
\[ F(3)=12,\qquad F(4)=360,\qquad F(8)=16785941760. \]
Такие проверки подтверждают саму комбинаторную формулу, а не только корректность модульных вычислений.
Предварительный расчет факториалов и обратных факториалов требует \(O(n)\) времени и \(O(n)\) памяти. В основной сумме \(n-1\) слагаемых, и для каждого из них выполняются два быстрых возведения в степень, так что общая сложность равна \(O(n\log n)\).
Для реального входа Euler, где \(n=100\), это очень мало. Но асимптотика все равно важна: эффективность достигается тем, что весь подсчет игры с камнями сведен к одной явной взвешенной сумме.
عند \(n=100\)، لا تقوم التطبيقات بمحاكاة Stone Game Solitaire حركةً بعد حركة. بدلًا من ذلك فهي تحسب عددًا تركيبيًا موزونًا بصيغة مغلقة modulo \(10^9+7\):
\[ F(n)= (n-1)! \cdot \frac12 \sum_{k=1}^{n-1} \binom{n}{k}\min(k,n-k)\,k^{k-1}(n-k)^{n-k-1}. \]
المسألة الرياضية الحقيقية هي تفسير سبب إمكان تنظيم الحالة الكاملة للعبة عبر تقسيم مميز إلى مجموعتين حجماهما \(k\) و\(n-k\)، ولماذا تعطي كل جهة عددًا من الأشجار الموسومة ذات الجذر، ولماذا تكون العوامل المتبقية بالضبط هي \(\min(k,n-k)\) و\(1/2\) و\((n-1)!\).
الحد داخل المجموع ليس حاصل ضرب اعتباطيًا. لكل عامل معنى تركيبي واضح، ومعًا تصف هذه العوامل البنى الموزونة التي تحسبها تطبيقات C++ وPython وJava.
تُصنّف التطبيقات المجموع الكلي وفق تفكيك مميز للحجارة \(n\) إلى جزأين غير فارغين حجماهما \(k\) و\(n-k\). وعندما يكون \(k\) ثابتًا، فإن اختيار أي الفهارس تقع في إحدى الجهتين يعطي العامل الثنائي
\[ \binom{n}{k}. \]
ولهذا ينهار كامل التحليل إلى مجموع واحد على \(k=1,2,\dots,n-1\). فبدل تتبع مجرى اللعبة كله مباشرة، يجري ترميزها عبر حجم إحدى جهتي هذا التقسيم المميز والبنى الموجودة على الجهتين.
تنص صيغة كايلي على أن عدد الأشجار الموسومة على \(m\) رؤوس هو \(m^{m-2}\). وإذا ميّزنا رأسًا إضافيًا بوصفه نقطة اتصال هذه الجهة ببقية البنية، فإن الشجرة تصبح متجذرة، وبذلك يُضرب العدد في \(m\):
\[ m \cdot m^{m-2}=m^{m-1}. \]
لذلك فإن تقسيمًا بحجمين \(k\) و\(n-k\) يساهم بالعامل
\[ k^{k-1}(n-k)^{n-k-1}, \]
وهو بالضبط عدد طرق اختيار شجرة موسومة ذات جذر على كل جانب. وباللغة التي تستعملها التطبيقات، فإن التاريخ الداخلي لكل جهة يُشفَّر بهاتين الشجرتين المتجذرتين.
الوزن الإضافي \(\min(k,n-k)\) يبيّن أن قيمة هذا التقسيم المميز تعتمد فقط على الجهة الأصغر. فإذا كان \(k<n/2\) كان الوزن هو \(k\)، وإذا كان \(k>n/2\) فإن الاختيار المتمم يصف التقسيم نفسه والجزء الأصغر نفسه.
وهذا التناظر يفسّر مباشرة وجود العامل الخارجي \(1/2\). فالعبارة
\[ \binom{n}{k}\min(k,n-k)\,k^{k-1}(n-k)^{n-k-1} \]
لا تتغير عند استبدال \(k\) بـ \(n-k\). لذا فإن الجمع على جميع القيم \(k=1,\dots,n-1\) يعدّ التقسيمات المتممة مرتين. والقسمة على 2 تعيد العد غير المرتب الصحيح، بما في ذلك الحالة الخاصة \(k=n/2\) عندما يتساوى الجانبان.
بعد عد البنية الموضعية حول التقسيم المميز، تضرب التطبيقات النتيجة في \((n-1)!\). وبما أن هذا العامل لا يعتمد على \(k\)، فهو يعمل كعامل ترتيب عام مشترك بين كل شكل تركيبي يظهر داخل المجموع.
وهذا الفصل مهم: فكل المعلومات البنيوية توجد داخل المجموع المتناظر على \(k\)، أما عامل ترتيب الحركات العام فيُطبَّق مرة واحدة فقط في النهاية.
عندما \(n=4\) تصبح الصيغة
\[ F(4)=3!\cdot \frac12 \left( \binom{4}{1}\cdot 1 \cdot 1^{0}\cdot 3^{2} + \binom{4}{2}\cdot 2 \cdot 2^{1}\cdot 2^{1} + \binom{4}{3}\cdot 1 \cdot 3^{2}\cdot 1^{0} \right). \]
الحالتان \(1+3\) و\(3+1\) تصفان الحجم نفسه بطريقة متممة، ولذلك يزيل العامل \(1/2\) هذا التكرار. عدديًا نحصل على
\[ F(4)=6\cdot \frac12 (36+48+36)=360. \]
وهذه إحدى القيم الصغيرة التي تُراجع بالحساب الصحيح الكامل، ولذلك فهي مثال ملموس يؤكد أن التفسير التركيبي منسجم مع التنفيذ.
بجمع كل الأجزاء معًا، فإن الكمية المحسوبة في Stone Game Solitaire هي
\[ \boxed{ F(n)= (n-1)! \cdot \frac12 \sum_{k=1}^{n-1} \binom{n}{k}\min(k,n-k)\,k^{k-1}(n-k)^{n-k-1} }. \]
وبمجرد معرفة هذه الهوية، لا تبقى المسألة تحليلًا تكراريًا للعبة، بل تصبح مجرد تقييم معياري سريع لالتفاف موزون واحد من أعداد الأشجار المتجذرة عند \(n=100\).
تحسب تطبيقات C++ وPython وJava المضروبات ومعكوسات المضروبات حتى \(n\) مسبقًا. وبما أن \(10^9+7\) عدد أولي، فإن كل معكوس يُستخرج من مبرهنة فيرما الصغرى:
\[ x^{-1}\equiv x^{10^9+5}\pmod{10^9+7}. \]
وبذلك يصبح كل معامل ثنائي الحد متاحًا في زمن ثابت عبر
\[ \binom{n}{k}=\frac{n!}{k!(n-k)!}\pmod{10^9+7}. \]
تمر الحلقة الرئيسية على \(k=1\) حتى \(n-1\). ولكل \(k\) تضرب الشيفرة العامل الثنائي ووزن الجهة الأصغر \(\min(k,n-k)\) وعاملي الأشجار المتجذرة. وتحسب القوتان \(k^{k-1}\) و\((n-k)^{n-k-1}\) بالأس السريع الثنائي، ولذلك فإن كلفة كل حد هي \(O(\log n)\) من العمليات الحسابية.
بعد جمع جميع الحدود modulo \(10^9+7\)، تُضرب النتيجة في المعكوس المعياري للعدد 2 ثم في \((n-1)!\). وترتيب هذه الخطوات يطابق الاشتقاق الرياضي تمامًا.
تعيد نسختا C++ وPython أيضًا حساب بعض القيم الصغيرة بحساب صحيح عادي قبل تطبيق الاختزال المعياري. وهي تتحقق من أن
\[ F(3)=12,\qquad F(4)=360,\qquad F(8)=16785941760. \]
وهذه الفحوصات تتحقق من صحة الصيغة التركيبية نفسها، لا من طبقة الحساب المعياري فقط.
يتطلب التحضير المسبق للمضروبات ومعكوساتها \(O(n)\) زمنًا و\(O(n)\) ذاكرة. أما المجموع الرئيسي ففيه \(n-1\) حدًا، وكل حد يحتاج إلى عمليتي أس سريعتين، لذا يكون الزمن الكلي \(O(n\log n)\).
وبالنسبة إلى دخل Euler الفعلي حيث \(n=100\)، فهذه الكلفة صغيرة جدًا. ومع ذلك فالوصف asymptotic مهم، لأن السرعة جاءت من ضغط عدّ اللعبة كله في مجموع موزون صريح واحد.