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\).
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.
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.
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.
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\).
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}.$$
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.
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.
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.
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.
Sei \(W(n)\) die Anzahl der Gewinnstellungen in der eingeschränkten \(n\)-Haufen-Nim-Variante, bei der jede Haufengröße eine verschiedene positive Zahl kleiner als \(2^n\) ist. Bei gewöhnlichem Nim ist eine Stellung genau dann verloren, wenn das bitweise XOR aller Haufengrößen null ist. Also müssen geordnete \(n\)-Tupel \((a_1,\dots,a_n)\) mit \(1 \le a_i \lt 2^n\), paarweise verschiedenen \(a_i\) und \(a_1\oplus\cdots\oplus a_n\ne 0\) gezählt werden; anschließend wird \(W(10^7)\bmod 10^9+7\) berechnet.
Jede Haufengröße wird binär geschrieben und mit einem Vektor aus \(G=\mathbb{F}_2^n\) identifiziert. Zulässig sind genau die von null verschiedenen Vektoren \(G^\ast=G\setminus\{0\}\), also \(|G^\ast|=2^n-1\). Da XOR in \(\mathbb{F}_2^n\) nichts anderes als Addition ist, sind Verluststellungen genau die Tupel mit
$$a_1+\cdots+a_n=0 \quad \text{in } \mathbb{F}_2^n.$$
Damit wird die Nim-Bedingung zu einer linearen Bedingung über dem Zweierkörper.
Setze \(q=2^n\). Ohne XOR-Bedingung wählt man \(n\) verschiedene Nichtnullvektoren in Reihenfolge. Also ist die Gesamtzahl
$$N_{\mathrm{all}}=(q-1)_n=\prod_{i=0}^{n-1}(q-1-i).$$
Das ist die vollständige Kandidatenmenge, bevor zwischen Verlust- und Gewinnstellungen getrennt wird.
Sei \(N_0\) die Anzahl der zulässigen Tupel mit XOR null. Für \(u\in G\) definiere den Charakter
$$\chi_u(x)=(-1)^{u\cdot x}.$$
Auf \(\mathbb{F}_2^n\) gilt die Orthogonalitätsrelation
$$\mathbf{1}_{x=0}=\frac{1}{q}\sum_{u\in G}\chi_u(x).$$
Für \(x=a_1+\cdots+a_n\) folgt daraus
$$N_0=\frac{1}{q}\sum_{u\in G}\sum_{\text{zulässige }(a_1,\dots,a_n)} \chi_u(a_1+\cdots+a_n).$$
Wegen \(\chi_u(x+y)=\chi_u(x)\chi_u(y)\) zerfällt das Gewicht des inneren Terms in ein Produkt über die einzelnen Haufengrößen.
Für den trivialen Charakter \(u=0\) ist die innere Summe einfach \(N_{\mathrm{all}}\). Sei nun \(u\ne 0\). Das lineare Funktional \(x\mapsto u\cdot x\) hat einen Kern der Größe \(q/2\). Daher gibt es unter allen \(q\) Vektoren genau \(q/2\) mit Charakterwert \(+1\) und \(q/2\) mit Charakterwert \(-1\). Nach Entfernen des Nullvektors bleiben
$$\frac{q}{2}-1 \text{ Werte mit } \chi_u(a)=1, \qquad \frac{q}{2} \text{ Werte mit } \chi_u(a)=-1.$$
Die gewichtete Summe über geordnete, paarweise verschiedene \(n\)-Tupel ist damit
$$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}.$$
Der Faktor \(n!\) entsteht, weil der Koeffizient ungeordnete Auswahlmengen zählt, die Nim-Stellungen hier aber als geordnete Tupel auftreten. Jeder nichttriviale Charakter liefert denselben Wert \(C_n\).
Schreibe \(r=2^{n-1}=q/2\) und \(m=\lfloor n/2 \rfloor\). Dann vereinfacht sich die erzeugende Funktion zu
$$ (1-x)^r(1+x)^{r-1}=(1-x)(1-x^2)^{r-1}. $$
Der gesuchte Koeffizient ist daher sofort
$$[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}$$
Somit gilt kompakt
$$C_n=(-1)^{\lceil n/2 \rceil} n!\binom{2^{n-1}-1}{\lfloor n/2 \rfloor}.$$
Es gibt genau einen trivialen Charakter und \(q-1\) nichttriviale Charaktere. Also
$$N_0=\frac{N_{\mathrm{all}}+(q-1)C_n}{q}.$$
Die Gewinnstellungen sind das Komplement:
$$\boxed{W(n)=N_{\mathrm{all}}-N_0.}$$
Genau diese Formel wird im Programm umgesetzt.
Hier ist \(q=8\), also gibt es \(7\) zulässige Haufengrößen. Die Gesamtzahl geordneter verschiedener Tripel ist
$$N_{\mathrm{all}}=7\cdot 6\cdot 5=210.$$
Außerdem gilt
$$C_3=3!\,[x^3](1-x)^4(1+x)^3=6\,[x^3](1-x)(1-x^2)^3.$$
Aus \((1-x^2)^3=1-3x^2+3x^4-x^6\) liest man für \((1-x)(1-x^2)^3\) den Koeffizienten \(3\) vor \(x^3\) ab. Damit ist \(C_3=18\), also
$$N_0=\frac{210+7\cdot 18}{8}=42,\qquad W(3)=210-42=168.$$
Das stimmt mit den Kontrollwerten der C++-, Python- und Java-Implementierungen überein.
Die C++-, Python- und Java-Implementierungen setzen die geschlossene Formel direkt um. Zuerst wird \(2^n \bmod 10^9+7\) berechnet, danach das fallende Fakultätsprodukt \((2^n-1)_n\) mit \(n\) modularen Multiplikationen. Für den Binomialterm wird bewusst keine Fakultät bis \(2^{n-1}-1\) aufgebaut; stattdessen wird der Zähler als fallendes Produkt der Länge \(\lfloor n/2 \rfloor\) gebildet, durch \(\lfloor n/2 \rfloor!\) per modularer Inversion geteilt und anschließend das paritätsabhängige Vorzeichen gesetzt.
Nach der Multiplikation mit \(n!\) kombiniert die Implementierung den trivialen und den nichttrivialen Charakterbeitrag, dividiert mittels modularer Inversion durch \(2^n\) und zieht die Verlustanzahl von der Gesamtanzahl ab. Die eingebauten Prüfpunkte \(W(1)=1\), \(W(2)=6\), \(W(3)=168\), \(W(5)=19764360\) und \(W(100)=384777056\) bestätigen die Herleitung.
Der dominierende Aufwand besteht aus wenigen Schleifen der Länge \(n\) beziehungsweise \(\lfloor n/2 \rfloor\). Deshalb beträgt die Laufzeit \(O(n)\). Gespeichert werden nur konstant viele modulare Akkumulatoren, also ist der Speicherverbrauch \(O(1)\). Genau diese lineare Zeit bei konstantem Speicher macht den Zielwert \(n=10^7\) praktikabel.
\(W(n)\), her yığın boyutunun \(2^n\)'den küçük, pozitif ve birbirinden farklı olduğu kısıtlı \(n\)-yığın Nim oyununun kazanan konumlarının sayısı olsun. Klasik Nim'de bir konum ancak ve ancak tüm yığın boyutlarının bit düzeyinde xor'u sıfırsa kaybedendir. Dolayısıyla amaç, \(1 \le a_i \lt 2^n\) koşulunu sağlayan, tüm \(a_i\)'leri farklı olan ve \(a_1\oplus\cdots\oplus a_n\ne 0\) veren sıralı \(n\)-lileri saymak, ardından \(W(10^7)\bmod 10^9+7\) değerini bulmaktır.
Her yığın boyutunu ikilik tabanda yazıp \(G=\mathbb{F}_2^n\) içindeki bir vektör olarak düşünelim. Geçerli yığın boyutları sıfır dışındaki vektörlerdir; yani \(G^\ast=G\setminus\{0\}\) ve \(|G^\ast|=2^n-1\). XOR işlemi \(\mathbb{F}_2^n\) içinde toplama ile aynı olduğundan, kaybeden konumlar tam olarak
$$a_1+\cdots+a_n=0 \quad \text{in } \mathbb{F}_2^n$$
eşitliğini sağlayan konumlardır. Böylece oyun koşulu lineer cebir diline indirgenir.
\(q=2^n\) olsun. XOR şartını bir an için unutursak, sıfır olmayan vektörlerden \(n\) tanesini sıralı ve farklı biçimde seçiyoruz. Toplam aday sayısı bu yüzden
$$N_{\mathrm{all}}=(q-1)_n=\prod_{i=0}^{n-1}(q-1-i)$$
olur. Bu sayı, kazanan-kaybeden ayrımı yapılmadan önceki tüm olası konumları verir.
XOR'u sıfır olan geçerli konum sayısına \(N_0\) diyelim. Her \(u\in G\) için
$$\chi_u(x)=(-1)^{u\cdot x}$$
karakterini tanımlayalım. \(\mathbb{F}_2^n\) üzerinde standart ortogonallik bağıntısı
$$\mathbf{1}_{x=0}=\frac{1}{q}\sum_{u\in G}\chi_u(x)$$
şeklindedir. Bunu \(x=a_1+\cdots+a_n\) için uygularsak
$$N_0=\frac{1}{q}\sum_{u\in G}\sum_{\text{geçerli }(a_1,\dots,a_n)} \chi_u(a_1+\cdots+a_n)$$
elde edilir. \(\chi_u(x+y)=\chi_u(x)\chi_u(y)\) olduğu için iç toplam çarpanlarına ayrılır.
Trivial karakter \(u=0\) için iç toplam doğrudan \(N_{\mathrm{all}}\)'dır. Şimdi \(u\ne 0\) sabitleyelim. \(x\mapsto u\cdot x\) lineer fonksiyonunun çekirdeği \(q/2\) elemanlıdır. Bu nedenle tüm \(q\) vektör arasında karakter değeri \(+1\) olan tam \(q/2\) vektör, \(-1\) olan tam \(q/2\) vektör vardır. Sıfır vektörü çıkarınca geriye
$$\frac{q}{2}-1 \text{ adet } \chi_u(a)=1, \qquad \frac{q}{2} \text{ adet } \chi_u(a)=-1$$
kalır. Farklı ve sıralı \(n\)-liler üzerindeki ağırlıklı toplam böylece
$$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}$$
olur. \(n!\) çarpanı, katsayının sırasız seçimleri saymasına karşın oyundaki konumların sıralı olmasından gelir. Her trivial olmayan karakter aynı \(C_n\) değerini üretir.
\(r=2^{n-1}=q/2\) ve \(m=\lfloor n/2 \rfloor\) olsun. Üreteç fonksiyon
$$ (1-x)^r(1+x)^{r-1}=(1-x)(1-x^2)^{r-1} $$
şeklinde sadeleşir. Bu yüzden istenen katsayı doğrudan
$$[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}$$
olur. Yani ortak katkı kompakt olarak
$$C_n=(-1)^{\lceil n/2 \rceil} n!\binom{2^{n-1}-1}{\lfloor n/2 \rfloor}$$
şeklindedir.
Bir tane trivial karakter, \(q-1\) tane de trivial olmayan karakter vardır. Dolayısıyla
$$N_0=\frac{N_{\mathrm{all}}+(q-1)C_n}{q}$$
elde edilir. Kazanan konum sayısı bunun tüm konumlardan çıkarılmasıyla bulunur:
$$\boxed{W(n)=N_{\mathrm{all}}-N_0.}$$
Uygulamanın kullandığı formül tam olarak budur.
Bu durumda \(q=8\) ve geçerli yığın boyutu sayısı \(7\)'dir. Farklı sıralı üçlülerin toplam sayısı
$$N_{\mathrm{all}}=7\cdot 6\cdot 5=210$$
olur. Ayrıca
$$C_3=3!\,[x^3](1-x)^4(1+x)^3=6\,[x^3](1-x)(1-x^2)^3.$$
\((1-x^2)^3=1-3x^2+3x^4-x^6\) olduğundan, \((1-x)(1-x^2)^3\) ifadesinde \(x^3\)'ün katsayısı \(3\)'tür. Böylece \(C_3=18\) ve
$$N_0=\frac{210+7\cdot 18}{8}=42,\qquad W(3)=210-42=168.$$
Bu sonuç C++, Python ve Java uygulamalarındaki kontrol değerleriyle aynıdır.
C++, Python ve Java uygulamaları kapalı formülü doğrudan hesaplar. Önce \(2^n \bmod 10^9+7\) bulunur, ardından \(n\) modüler çarpımla \((2^n-1)_n\) hesaplanır. Binom terimi için \(2^{n-1}-1\)'e kadar faktöriyel oluşturulmaz; bunun yerine uzunluğu \(\lfloor n/2 \rfloor\) olan bir düşen çarpım alınır, \(\lfloor n/2 \rfloor!\) modüler ters ile bölünür ve sonra işaret \(n\)'in tek-çift oluşuna göre ayarlanır.
Son adımda \(n!\) ile çarpılır, trivial ve trivial olmayan karakter katkıları birleştirilir, \(2^n\)'ye modüler ters üzerinden bölünür ve kaybeden konum sayısı toplamdan çıkarılır. Yerleşik kontrol noktaları \(W(1)=1\), \(W(2)=6\), \(W(3)=168\), \(W(5)=19764360\) ve \(W(100)=384777056\) türetimi doğrular.
Baskın maliyet, uzunluğu \(n\) veya \(\lfloor n/2 \rfloor\) olan birkaç döngüdür; bu yüzden zaman karmaşıklığı \(O(n)\)'dir. Saklanan veriler yalnızca sabit sayıda modüler akümülatörden oluşur, dolayısıyla bellek kullanımı \(O(1)\)'dir. Bu lineer zaman ve sabit bellek yapısı, \(n=10^7\) hedefini uygulanabilir kılar.
Sea \(W(n)\) el número de posiciones ganadoras en la variante restringida de Nim con \(n\) montones, donde cada tamaño de montón es un entero positivo distinto menor que \(2^n\). En el Nim clásico una posición es perdedora exactamente cuando el xor bit a bit de todos los montones es cero. Por tanto, hay que contar \(n\)-tuplas ordenadas \((a_1,\dots,a_n)\) con \(1 \le a_i \lt 2^n\), todos los \(a_i\) distintos y \(a_1\oplus\cdots\oplus a_n\ne 0\), y luego evaluar \(W(10^7)\bmod 10^9+7\).
Escribimos cada tamaño de montón en binario y lo identificamos con un vector de \(G=\mathbb{F}_2^n\). Los tamaños permitidos son los vectores no nulos \(G^\ast=G\setminus\{0\}\), así que \(|G^\ast|=2^n-1\). Como el xor coincide con la suma en \(\mathbb{F}_2^n\), una posición perdedora satisface exactamente
$$a_1+\cdots+a_n=0 \quad \text{in } \mathbb{F}_2^n.$$
De este modo, la condición del juego se convierte en una restricción lineal.
Sea \(q=2^n\). Si ignoramos momentáneamente la condición del xor, elegimos \(n\) vectores no nulos distintos en orden. El número total de candidatos es entonces
$$N_{\mathrm{all}}=(q-1)_n=\prod_{i=0}^{n-1}(q-1-i).$$
Ese es el total de posiciones admisibles antes de separar perdedoras y ganadoras.
Denotemos por \(N_0\) el número de tuplas admisibles con xor cero. Para cada \(u\in G\), definimos el carácter
$$\chi_u(x)=(-1)^{u\cdot x}.$$
La identidad de ortogonalidad en \(\mathbb{F}_2^n\) es
$$\mathbf{1}_{x=0}=\frac{1}{q}\sum_{u\in G}\chi_u(x).$$
Aplicada a \(x=a_1+\cdots+a_n\), produce
$$N_0=\frac{1}{q}\sum_{u\in G}\sum_{\text{tuplas admisibles }(a_1,\dots,a_n)} \chi_u(a_1+\cdots+a_n).$$
Como \(\chi_u(x+y)=\chi_u(x)\chi_u(y)\), el peso interior se factoriza como producto sobre los elementos elegidos.
Para el carácter trivial \(u=0\), la suma interior vale simplemente \(N_{\mathrm{all}}\). Fijemos ahora \(u\ne 0\). El funcional lineal \(x\mapsto u\cdot x\) tiene núcleo de tamaño \(q/2\), de modo que entre los \(q\) vectores hay exactamente \(q/2\) con valor \(+1\) y \(q/2\) con valor \(-1\). Al excluir el vector nulo quedan
$$\frac{q}{2}-1 \text{ valores con } \chi_u(a)=1, \qquad \frac{q}{2} \text{ valores con } \chi_u(a)=-1.$$
La suma ponderada sobre \(n\)-tuplas ordenadas y distintas es entonces
$$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}.$$
El factor \(n!\) aparece porque el coeficiente cuenta subconjuntos no ordenados de tamaño \(n\), mientras que aquí las posiciones se consideran ordenadas. Todos los caracteres no triviales producen el mismo \(C_n\).
Sea \(r=2^{n-1}=q/2\) y \(m=\lfloor n/2 \rfloor\). La función generadora se simplifica a
$$ (1-x)^r(1+x)^{r-1}=(1-x)(1-x^2)^{r-1}. $$
Por tanto, el coeficiente buscado es
$$[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}$$
En forma compacta,
$$C_n=(-1)^{\lceil n/2 \rceil} n!\binom{2^{n-1}-1}{\lfloor n/2 \rfloor}.$$
Hay un carácter trivial y \(q-1\) caracteres no triviales. En consecuencia,
$$N_0=\frac{N_{\mathrm{all}}+(q-1)C_n}{q}.$$
Las posiciones ganadoras son el complemento:
$$\boxed{W(n)=N_{\mathrm{all}}-N_0.}$$
Esa es exactamente la fórmula implementada.
Aquí \(q=8\), así que hay \(7\) tamaños de montón admisibles. El número total de ternas ordenadas y distintas es
$$N_{\mathrm{all}}=7\cdot 6\cdot 5=210.$$
Además,
$$C_3=3!\,[x^3](1-x)^4(1+x)^3=6\,[x^3](1-x)(1-x^2)^3.$$
Como \((1-x^2)^3=1-3x^2+3x^4-x^6\), el coeficiente de \(x^3\) en \((1-x)(1-x^2)^3\) es \(3\). Por tanto \(C_3=18\), y
$$N_0=\frac{210+7\cdot 18}{8}=42,\qquad W(3)=210-42=168.$$
Esto coincide con los puntos de control usados por las implementaciones en C++, Python y Java.
Las implementaciones en C++, Python y Java siguen directamente la forma cerrada. Primero calculan \(2^n \bmod 10^9+7\), después evalúan el factorial descendente \((2^n-1)_n\) con \(n\) multiplicaciones modulares. Para el término binomial no construyen factoriales hasta \(2^{n-1}-1\); en su lugar forman el numerador como un producto descendente de longitud \(\lfloor n/2 \rfloor\), dividen por \(\lfloor n/2 \rfloor!\) usando un inverso modular y luego aplican el signo según la paridad de \(n\).
Tras multiplicar por \(n!\), la implementación combina la contribución trivial con la no trivial, divide por \(2^n\) mediante el inverso modular y resta la cuenta de posiciones perdedoras del total. Los chequeos \(W(1)=1\), \(W(2)=6\), \(W(3)=168\), \(W(5)=19764360\) y \(W(100)=384777056\) verifican la derivación.
El trabajo dominante son unas pocas iteraciones de longitud \(n\) o \(\lfloor n/2 \rfloor\), por lo que el tiempo total es \(O(n)\). Solo se almacenan unos cuantos acumuladores modulares, así que la memoria es \(O(1)\). Esa estructura de tiempo lineal y espacio constante es la razón por la que el caso objetivo \(n=10^7\) sigue siendo viable.
设 \(W(n)\) 表示受限 \(n\) 堆 Nim 中的必胜局面数，其中每一堆的大小都是小于 \(2^n\) 的互不相同的正整数。普通 Nim 的判定条件是：当且仅当所有堆大小的按位 xor 为零时，该局面是必败局面。因此问题等价于统计满足 \(1 \le a_i \lt 2^n\)、各 \(a_i\) 互不相同且 \(a_1\oplus\cdots\oplus a_n\ne 0\) 的有序 \(n\) 元组 \((a_1,\dots,a_n)\)，然后求 \(W(10^7)\bmod 10^9+7\)。
把每个堆大小写成二进制，并看作 \(G=\mathbb{F}_2^n\) 中的一个向量。允许的堆大小正好对应非零向量 \(G^\ast=G\setminus\{0\}\)，所以 \(|G^\ast|=2^n-1\)。由于 xor 在 \(\mathbb{F}_2^n\) 中就是向量加法，必败局面恰好满足
$$a_1+\cdots+a_n=0 \quad \text{in } \mathbb{F}_2^n.$$
这样一来，游戏条件就变成了一个线性代数约束。
记 \(q=2^n\)。先忽略 xor 条件，只需按顺序选出 \(n\) 个互不相同的非零向量，因此总数为下降阶乘
$$N_{\mathrm{all}}=(q-1)_n=\prod_{i=0}^{n-1}(q-1-i).$$
这就是在区分必败与必胜之前的全部候选局面数。
设 \(N_0\) 为 xor 为零的合法元组数。对每个 \(u\in G\)，定义特征
$$\chi_u(x)=(-1)^{u\cdot x}.$$
在 \(\mathbb{F}_2^n\) 上有标准正交恒等式
$$\mathbf{1}_{x=0}=\frac{1}{q}\sum_{u\in G}\chi_u(x).$$
把它应用到 \(x=a_1+\cdots+a_n\) 上，就得到
$$N_0=\frac{1}{q}\sum_{u\in G}\sum_{\text{合法 }(a_1,\dots,a_n)} \chi_u(a_1+\cdots+a_n).$$
又因为 \(\chi_u(x+y)=\chi_u(x)\chi_u(y)\)，内层权重可以拆成对每个已选元素的乘积。
对平凡特征 \(u=0\)，内层求和显然就是 \(N_{\mathrm{all}}\)。现在固定 \(u\ne 0\)。线性函数 \(x\mapsto u\cdot x\) 的核大小为 \(q/2\)，所以在全部 \(q\) 个向量中，恰有 \(q/2\) 个取值为 \(+1\)，也恰有 \(q/2\) 个取值为 \(-1\)。去掉零向量后，非零集合中还剩
$$\frac{q}{2}-1 \text{ 个满足 } \chi_u(a)=1,\qquad \frac{q}{2} \text{ 个满足 } \chi_u(a)=-1.$$
于是对互不相同的有序 \(n\) 元组求加权和可写成
$$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}.$$
其中 \(n!\) 的原因是：系数提取本质上先统计不计顺序的 \(n\) 元集合，而题目要求的是有序元组。所有非平凡特征给出的 \(C_n\) 完全相同。
设 \(r=2^{n-1}=q/2\)，\(m=\lfloor n/2 \rfloor\)。生成函数化简为
$$ (1-x)^r(1+x)^{r-1}=(1-x)(1-x^2)^{r-1}. $$
因此所需系数立刻得到
$$[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}$$
从而公共贡献可写成紧凑形式
$$C_n=(-1)^{\lceil n/2 \rceil} n!\binom{2^{n-1}-1}{\lfloor n/2 \rfloor}.$$
共有一个平凡特征和 \(q-1\) 个非平凡特征，因此
$$N_0=\frac{N_{\mathrm{all}}+(q-1)C_n}{q}.$$
必胜局面数就是总数减去必败数：
$$\boxed{W(n)=N_{\mathrm{all}}-N_0.}$$
这正是程序实现的核心公式。
此时 \(q=8\)，所以共有 \(7\) 个合法堆大小。全部互异有序三元组的总数是
$$N_{\mathrm{all}}=7\cdot 6\cdot 5=210.$$
另一方面，
$$C_3=3!\,[x^3](1-x)^4(1+x)^3=6\,[x^3](1-x)(1-x^2)^3.$$
因为 \((1-x^2)^3=1-3x^2+3x^4-x^6\)，所以 \((1-x)(1-x^2)^3\) 中 \(x^3\) 的系数为 \(3\)。于是 \(C_3=18\)，从而
$$N_0=\frac{210+7\cdot 18}{8}=42,\qquad W(3)=210-42=168.$$
这与 C++、Python 和 Java 实现中的校验值一致。
C++、Python 和 Java 实现都直接按照闭式公式计算。它们先求 \(2^n \bmod 10^9+7\)，再用 \(n\) 次模乘得到下降阶乘 \((2^n-1)_n\)。对于二项式项，并不会构造到 \(2^{n-1}-1\) 为止的巨大阶乘，而是只构造长度为 \(\lfloor n/2 \rfloor\) 的下降乘积，再用 \(\lfloor n/2 \rfloor!\) 的模逆完成除法，最后根据 \(n\) 的奇偶性补上符号。
随后实现把结果乘上 \(n!\)，合并平凡特征与非平凡特征的贡献，再通过 \(2^n\) 的模逆完成除法，最后用总数减去必败数。校验点 \(W(1)=1\)、\(W(2)=6\)、\(W(3)=168\)、\(W(5)=19764360\)、\(W(100)=384777056\) 说明这一推导是正确的。
主要工作来自少数几个长度为 \(n\) 或 \(\lfloor n/2 \rfloor\) 的循环，因此总时间复杂度是 \(O(n)\)。程序只保存常数个模运算累加器，所以额外空间复杂度是 \(O(1)\)。正因为如此，目标规模 \(n=10^7\) 仍然可计算。
Пусть \(W(n)\) обозначает число выигрышных позиций в ограниченном варианте Nim с \(n\) кучами, где размер каждой кучи является различным положительным числом, меньшим \(2^n\). В обычном Nim позиция проигрышна тогда и только тогда, когда побитовое xor всех размеров равно нулю. Значит, нужно посчитать упорядоченные \(n\)-кортежи \((a_1,\dots,a_n)\) с условиями \(1 \le a_i \lt 2^n\), все \(a_i\) различны и \(a_1\oplus\cdots\oplus a_n\ne 0\), а затем вычислить \(W(10^7)\bmod 10^9+7\).
Каждый размер кучи записывается в двоичном виде и рассматривается как вектор из \(G=\mathbb{F}_2^n\). Допустимые размеры кучи соответствуют ненулевым векторам \(G^\ast=G\setminus\{0\}\), поэтому \(|G^\ast|=2^n-1\). Поскольку xor в \(\mathbb{F}_2^n\) совпадает со сложением, проигрышные позиции задаются условием
$$a_1+\cdots+a_n=0 \quad \text{in } \mathbb{F}_2^n.$$
Тем самым игровое условие превращается в линейное ограничение.
Положим \(q=2^n\). Если временно забыть про условие xor, нужно выбрать \(n\) различных ненулевых векторов с учетом порядка. Поэтому общее число вариантов равно
$$N_{\mathrm{all}}=(q-1)_n=\prod_{i=0}^{n-1}(q-1-i).$$
Это все допустимые позиции до разделения на проигрышные и выигрышные.
Обозначим через \(N_0\) число допустимых кортежей с xor, равным нулю. Для каждого \(u\in G\) введем характер
$$\chi_u(x)=(-1)^{u\cdot x}.$$
На \(\mathbb{F}_2^n\) справедливо стандартное соотношение ортогональности
$$\mathbf{1}_{x=0}=\frac{1}{q}\sum_{u\in G}\chi_u(x).$$
Подставляя \(x=a_1+\cdots+a_n\), получаем
$$N_0=\frac{1}{q}\sum_{u\in G}\sum_{\text{допустимые }(a_1,\dots,a_n)} \chi_u(a_1+\cdots+a_n).$$
Так как \(\chi_u(x+y)=\chi_u(x)\chi_u(y)\), внутренний вес раскладывается в произведение по выбранным элементам.
Для тривиального характера \(u=0\) внутренняя сумма просто равна \(N_{\mathrm{all}}\). Теперь зафиксируем \(u\ne 0\). Линейный функционал \(x\mapsto u\cdot x\) имеет ядро размера \(q/2\), поэтому среди всех \(q\) векторов ровно \(q/2\) дают значение \(+1\) и ровно \(q/2\) дают значение \(-1\). После исключения нулевого вектора в ненулевом множестве остается
$$\frac{q}{2}-1 \text{ значений с } \chi_u(a)=1,\qquad \frac{q}{2} \text{ значений с } \chi_u(a)=-1.$$
Следовательно, взвешенная сумма по различным упорядоченным \(n\)-кортежам имеет вид
$$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}.$$
Множитель \(n!\) появляется потому, что коэффициент сначала считает неупорядоченный выбор \(n\) различных элементов, а позиции Nim здесь считаются упорядоченными. Для любого нетривиального характера получается одно и то же значение \(C_n\).
Пусть \(r=2^{n-1}=q/2\) и \(m=\lfloor n/2 \rfloor\). Тогда производящая функция упрощается:
$$ (1-x)^r(1+x)^{r-1}=(1-x)(1-x^2)^{r-1}. $$
Отсюда немедленно следует
$$[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}$$
Значит, общий вклад можно записать компактно:
$$C_n=(-1)^{\lceil n/2 \rceil} n!\binom{2^{n-1}-1}{\lfloor n/2 \rfloor}.$$
Есть один тривиальный характер и \(q-1\) нетривиальных, поэтому
$$N_0=\frac{N_{\mathrm{all}}+(q-1)C_n}{q}.$$
Число выигрышных позиций равно дополнению:
$$\boxed{W(n)=N_{\mathrm{all}}-N_0.}$$
Именно эта формула реализована в программе.
Здесь \(q=8\), то есть допустимых размеров кучи \(7\). Общее число различных упорядоченных троек равно
$$N_{\mathrm{all}}=7\cdot 6\cdot 5=210.$$
Кроме того,
$$C_3=3!\,[x^3](1-x)^4(1+x)^3=6\,[x^3](1-x)(1-x^2)^3.$$
Так как \((1-x^2)^3=1-3x^2+3x^4-x^6\), коэффициент при \(x^3\) в \((1-x)(1-x^2)^3\) равен \(3\). Следовательно, \(C_3=18\), и
$$N_0=\frac{210+7\cdot 18}{8}=42,\qquad W(3)=210-42=168.$$
Это совпадает с контрольными значениями из реализаций на C++, Python и Java.
Реализации на C++, Python и Java напрямую используют полученную закрытую формулу. Сначала вычисляется \(2^n \bmod 10^9+7\), затем за \(n\) модульных умножений строится падающий факториал \((2^n-1)_n\). Для биномиального члена не строятся факториалы вплоть до \(2^{n-1}-1\); вместо этого числитель собирается как падающее произведение длины \(\lfloor n/2 \rfloor\), деление на \(\lfloor n/2 \rfloor!\) выполняется через модульный обратный элемент, а затем применяется знак в зависимости от четности \(n\).
После умножения на \(n!\) программа объединяет тривиальный и нетривиальный вклады, делит на \(2^n\) через модульный обратный элемент и вычитает число проигрышных позиций из общего количества. Контрольные значения \(W(1)=1\), \(W(2)=6\), \(W(3)=168\), \(W(5)=19764360\) и \(W(100)=384777056\) подтверждают корректность вывода.
Основная работа состоит из нескольких циклов длины \(n\) или \(\lfloor n/2 \rfloor\), поэтому время работы равно \(O(n)\). Хранятся лишь несколько модульных накопителей, так что память равна \(O(1)\). Именно линейное время и постоянная память делают достижимым целевое значение \(n=10^7\).
ليكن \(W(n)\) عدد الوضعيات الرابحة في نسخة Nim المقيّدة ذات \(n\) أكوام، حيث يكون حجم كل كومة عددًا صحيحًا موجبًا مختلفًا عن البقية وأصغر من \(2^n\). في Nim التقليدية تكون الوضعية خاسرة إذا وفقط إذا كان xor الثنائي لجميع أحجام الأكوام يساوي الصفر. لذلك تصبح المهمة هي عدّ جميع الأزواج المرتبة \((a_1,\dots,a_n)\) التي تحقق \(1 \le a_i \lt 2^n\)، وجميع \(a_i\) مختلفة، و\(a_1\oplus\cdots\oplus a_n\ne 0\)، ثم حساب \(W(10^7)\bmod 10^9+7\).
نكتب كل حجم كومة بالثنائي ونمثّله كمتجه في \(G=\mathbb{F}_2^n\). القيم المسموح بها هي المتجهات غير الصفرية فقط، أي \(G^\ast=G\setminus\{0\}\)، ولذلك \(|G^\ast|=2^n-1\). وبما أن xor يطابق الجمع في \(\mathbb{F}_2^n\)، فإن الوضعيات الخاسرة هي بالضبط تلك التي تحقق
$$a_1+\cdots+a_n=0 \quad \text{in } \mathbb{F}_2^n.$$
وهكذا تتحول قاعدة اللعبة إلى قيد خطي واضح.
لنضع \(q=2^n\). إذا تجاهلنا شرط xor مؤقتًا، فنحن نختار \(n\) متجهات غير صفرية ومختلفة مع اعتبار الترتيب. إذن العدد الكلي هو
$$N_{\mathrm{all}}=(q-1)_n=\prod_{i=0}^{n-1}(q-1-i).$$
وهذا هو عدد جميع الوضعيات المرشحة قبل فصل الخاسر من الرابح.
لنرمز بعدد الأزواج المسموح بها ذات xor الصفري بالرمز \(N_0\). ولكل \(u\in G\) نعرّف المحرف
$$\chi_u(x)=(-1)^{u\cdot x}.$$
وتتحقق علاقة التعامد القياسية على \(\mathbb{F}_2^n\):
$$\mathbf{1}_{x=0}=\frac{1}{q}\sum_{u\in G}\chi_u(x).$$
إذا رمزنا لمجموعة الأزواج المرتبة المسموح بها بالرمز \(\mathcal{A}_n\)، فإن تطبيق هذه العلاقة على \(x=a_1+\cdots+a_n\) يعطي
$$N_0=\frac{1}{q}\sum_{u\in G}\sum_{(a_1,\dots,a_n)\in \mathcal{A}_n} \chi_u(a_1+\cdots+a_n).$$
ولأن \(\chi_u(x+y)=\chi_u(x)\chi_u(y)\)، فإن الوزن داخل المجموع يتفكك إلى حاصل ضرب على العناصر المختارة.
إذا كان \(u=0\) فالمجموع الداخلي يساوي مباشرة \(N_{\mathrm{all}}\). أما إذا أخذنا \(u\ne 0\)، فإن الدالة الخطية \(x\mapsto u\cdot x\) نواتها تحوي \(q/2\) عنصرًا. لذلك يوجد بين جميع متجهات \(G\) عدد مقداره \(q/2\) يعطي القيمة \(+1\)، وعدد مقداره \(q/2\) يعطي القيمة \(-1\). وبعد حذف المتجه الصفري يصبح توزع القيم في المجموعة غير الصفرية
$$\#\{a\in G^\ast:\chi_u(a)=1\}=\frac{q}{2}-1,\qquad \#\{a\in G^\ast:\chi_u(a)=-1\}=\frac{q}{2}.$$
ومن ثم فإن المجموع الموزون على الأزواج المرتبة المختلفة يصبح
$$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}.$$
ويظهر العامل \(n!\) لأن استخراج المعامل يعدّ أولًا اختيارات غير مرتبة من \(n\) عناصر مختلفة، بينما الوضعيات هنا مرتبة. وجميع المحارف غير التافهة تعطي نفس القيمة \(C_n\).
لنضع \(r=2^{n-1}=q/2\) و\(m=\lfloor n/2 \rfloor\). عندئذ تتبسط الدالة المولدة إلى
$$ (1-x)^r(1+x)^{r-1}=(1-x)(1-x^2)^{r-1}. $$
ومنها نحصل مباشرة على
$$[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}$$
إذًا يمكن كتابة المساهمة المشتركة على الصورة المدمجة
$$C_n=(-1)^{\lceil n/2 \rceil} n!\binom{2^{n-1}-1}{\lfloor n/2 \rfloor}.$$
لدينا محرف تافه واحد و\(q-1\) محارف غير تافهة، ولذلك
$$N_0=\frac{N_{\mathrm{all}}+(q-1)C_n}{q}.$$
أما عدد الوضعيات الرابحة فهو المتمم:
$$\boxed{W(n)=N_{\mathrm{all}}-N_0.}$$
وهذه هي الصيغة التي تعتمدها التطبيقات حرفيًا.
هنا \(q=8\)، وبالتالي يوجد \(7\) أحجام أكوام مسموح بها. وعدد الثلاثيات المرتبة المختلفة هو
$$N_{\mathrm{all}}=7\cdot 6\cdot 5=210.$$
كذلك لدينا
$$C_3=3!\,[x^3](1-x)^4(1+x)^3=6\,[x^3](1-x)(1-x^2)^3.$$
وبما أن \((1-x^2)^3=1-3x^2+3x^4-x^6\)، فإن معامل \(x^3\) في \((1-x)(1-x^2)^3\) يساوي \(3\). إذن \(C_3=18\)، ومن ثم
$$N_0=\frac{210+7\cdot 18}{8}=42,\qquad W(3)=210-42=168.$$
وهذا يطابق قيم التحقق المستخدمة في تطبيقات C++ وPython وJava.
تتبع تطبيقات C++ وPython وJava الصيغة المغلقة مباشرة. فهي تحسب أولًا \(2^n \bmod 10^9+7\)، ثم تبني المضروب الهابط \((2^n-1)_n\) عبر \(n\) ضربات معيارية. أما الحد الثنائي فلا يُحسب باستعمال مضاريب هائلة حتى \(2^{n-1}-1\)، بل يُبنى البسط كحاصل ضرب هابط طوله \(\lfloor n/2 \rfloor\)، ثم تتم القسمة على \(\lfloor n/2 \rfloor!\) باستخدام المعكوس المعياري، وبعد ذلك تُطبَّق الإشارة المناسبة حسب زوجية \(n\).
بعد الضرب في \(n!\)، يجمع التنفيذ بين مساهمة المحرف التافه ومساهمة المحارف غير التافهة، ثم يقسم على \(2^n\) عبر المعكوس المعياري، وأخيرًا يطرح عدد الوضعيات الخاسرة من العدد الكلي. وقيم التحقق \(W(1)=1\)، \(W(2)=6\)، \(W(3)=168\)، \(W(5)=19764360\)، و\(W(100)=384777056\) تؤكد صحة الاشتقاق.
العمل الغالب هو عدد قليل من الحلقات بطول \(n\) أو \(\lfloor n/2 \rfloor\)، لذلك زمن التنفيذ هو \(O(n)\). أما الذاكرة الإضافية فهي \(O(1)\) لأن التنفيذ يحتفظ بعدد ثابت فقط من المراكمات المعيارية. وهذا بالضبط ما يجعل الحالة المستهدفة \(n=10^7\) ممكنة عمليًا.