Detailed mathematical approach

Problem Summary

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

Mathematical Approach

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.

Grouping complete plays by a distinguished split

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.

Why \(k^{k-1}\) and \((n-k)^{n-k-1}\) appear

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 smaller-side weight and the factor \(1/2\)

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.

The role of the global factor \((n-1)!\)

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.

Worked example: \(n=4\)

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.

Final closed form

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

How the Code Works

Precomputing combinations modulo a prime

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}. \]

Evaluating the weighted rooted-tree sum

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.

Exact sanity checks on small inputs

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.

Complexity Analysis

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.

Footnotes and References

1. Problem page: https://projecteuler.net/problem=960
2. Cayley's formula: Wikipedia - Cayley's formula
3. Prüfer sequence: Wikipedia - Prüfer sequence
4. Binomial coefficient: Wikipedia - Binomial coefficient
5. Modular exponentiation: Wikipedia - Modular exponentiation
6. Fermat's little theorem: Wikipedia - Fermat's little theorem