Detailed mathematical approach

Problem Summary

Let \(W(n)\) denote the number of winning positions in the constrained \(n\)-heap Nim variant where each heap size is a distinct positive integer smaller than \(2^n\). In ordinary Nim, a position is losing exactly when the bitwise xor of all heap sizes is zero, so the task is to count ordered \(n\)-tuples \((a_1,\dots,a_n)\) with \(1 \le a_i \lt 2^n\), all \(a_i\) different, and \(a_1 \oplus \cdots \oplus a_n \ne 0\), then evaluate \(W(10^7)\bmod 10^9+7\).

Mathematical Approach

Step 1: Rewrite the game in \(\mathbb{F}_2^n\)

Write each heap size in binary and identify it with a vector in \(G=\mathbb{F}_2^n\). The admissible heap sizes are the nonzero vectors \(G^\ast=G\setminus\{0\}\), so \(|G^\ast|=2^n-1\). Because xor is addition in \(\mathbb{F}_2^n\), a position is losing precisely when

$a_1+\cdots+a_n=0 \quad \text{in } \mathbb{F}_2^n.$

This turns the Nim condition into a clean linear-algebraic constraint.

Step 2: Count all admissible ordered tuples

Set \(q=2^n\). Ignoring the xor condition, we choose \(n\) distinct nonzero vectors in order. Therefore the total number of admissible tuples is the falling factorial

$N_{\mathrm{all}}=(q-1)_n=\prod_{i=0}^{n-1}(q-1-i).$

This is the count of all candidate positions before separating losing from winning ones.

Step 3: Detect xor-zero tuples with additive characters

Let \(N_0\) be the number of admissible tuples with xor zero. For each \(u\in G\), define the character

$\chi_u(x)=(-1)^{u\cdot x}.$

The standard orthogonality identity on \(\mathbb{F}_2^n\) is

$\mathbf{1}_{x=0}=\frac{1}{q}\sum_{u\in G}\chi_u(x).$

Applying this to \(x=a_1+\cdots+a_n\) gives

$N_0=\frac{1}{q}\sum_{u\in G}\sum_{\text{admissible }(a_1,\dots,a_n)} \chi_u(a_1+\cdots+a_n).$

Since \(\chi_u(x+y)=\chi_u(x)\chi_u(y)\), the inner weight factors into a product over the chosen heap sizes.

Step 4: Evaluate the common nontrivial character contribution

For the trivial character \(u=0\), the inner sum is simply \(N_{\mathrm{all}}\). Now fix \(u\ne 0\). The linear functional \(x\mapsto u\cdot x\) has kernel of size \(q/2\), so among all \(q\) vectors there are exactly \(q/2\) values with character \(+1\) and \(q/2\) values with character \(-1\). After removing the zero vector, the nonzero set contains

$\frac{q}{2}-1 \text{ values with } \chi_u(a)=1, \qquad \frac{q}{2} \text{ values with } \chi_u(a)=-1.$

If we sum \(\prod_{i=1}^n \chi_u(a_i)\) over distinct ordered \(n\)-tuples, we obtain

$C_n=n!\,[x^n]\prod_{a\in G^\ast}(1+\chi_u(a)x)=n!\,[x^n](1-x)^{q/2}(1+x)^{q/2-1}.$

The factor \(n!\) appears because the coefficient counts unordered choices of \(n\) distinct elements, while the Nim positions are ordered tuples. Every nontrivial character yields the same value \(C_n\).

Step 5: Collapse the coefficient to a single binomial term

Let \(r=2^{n-1}=q/2\) and \(m=\lfloor n/2 \rfloor\). The generating function simplifies to

$ (1-x)^{r}(1+x)^{r-1}=(1-x)(1-x^2)^{r-1}. $

Hence the coefficient is immediate:

$[x^n](1-x)(1-x^2)^{r-1}= \begin{cases} (-1)^m \binom{r-1}{m}, & n=2m, \\ (-1)^{m+1} \binom{r-1}{m}, & n=2m+1. \end{cases}$

So the common nontrivial contribution can be written compactly as

$C_n=(-1)^{\lceil n/2 \rceil} n!\binom{2^{n-1}-1}{\lfloor n/2 \rfloor}.$

Step 6: Losing and winning positions

There is one trivial character and \(q-1\) nontrivial characters. Therefore

$N_0=\frac{N_{\mathrm{all}}+(q-1)C_n}{q}.$

The winning positions are the complement:

$\boxed{W(n)=N_{\mathrm{all}}-N_0.}$

This is the exact formula used by the implementation.

Worked Example: \(n=3\)

Now \(q=8\), so there are \(7\) admissible heap sizes. The total number of ordered distinct triples is

$N_{\mathrm{all}}=7\cdot 6\cdot 5=210.$

Also

$C_3=3!\,[x^3](1-x)^4(1+x)^3=6\,[x^3](1-x)(1-x^2)^3.$

Since \((1-x^2)^3=1-3x^2+3x^4-x^6\), the coefficient of \(x^3\) in \((1-x)(1-x^2)^3\) is \(3\). Thus \(C_3=18\), and

$N_0=\frac{210+7\cdot 18}{8}=42,\qquad W(3)=210-42=168.$

This matches the checkpoint values used by the C++, Python, and Java implementations.

How the Code Works

The C++, Python, and Java implementations follow the closed form directly. They compute \(2^n \bmod 10^9+7\), then evaluate the falling factorial \((2^n-1)_n\) with \(n\) modular multiplications. For the binomial term they avoid any factorial up to \(2^{n-1}-1\); instead they build the numerator as a falling product of length \(\lfloor n/2 \rfloor\), divide by \(\lfloor n/2 \rfloor!\) through a modular inverse, and then apply the sign determined by the parity of \(n\).

After multiplying by \(n!\), the implementation combines the trivial and nontrivial character contributions, divides by \(2^n\) via a modular inverse, and subtracts the losing count from the total count. The built-in checkpoints \(W(1)=1\), \(W(2)=6\), \(W(3)=168\), \(W(5)=19764360\), and \(W(100)=384777056\) confirm the derivation.

Complexity Analysis

The dominant work consists of a few loops of length \(n\) or \(\lfloor n/2 \rfloor\), so the running time is \(O(n)\). Only a constant number of modular accumulators are stored, hence the memory usage is \(O(1)\). That linear-time, constant-space structure is exactly what makes the target \(n=10^7\) feasible.

Footnotes and References

1. Problem page: https://projecteuler.net/problem=409
2. Nim and xor criterion: Wikipedia — Nim
3. Character groups and orthogonality: Wikipedia — Character group
4. Generating functions: Wikipedia — Generating function
5. Falling factorial notation: Wikipedia — Falling and rising factorials