Problem 976, XO Game, is solved in the implementations by a pure counting argument modulo \(1234567891\). For the target input \(N=10^7\), the only case that matters is \(N\equiv 0 \pmod 4\), so the game analysis collapses to three explicit combinatorial blocks instead of any game-tree search, dynamic programming, or simulation.
The key invariant visible in all three implementations is parity. The final answer is assembled from the number of even-parity game states, corrected by subtracting the even-parity states that are losing and adding the odd-parity states that are winning. Once that split has been proved, the whole problem becomes a sequence of binomial-coefficient summations.
Let
$$M=1234567891,\qquad N_o=\frac N2,\qquad N_a=\frac N4.$$
For the actual Project Euler input, this means \(N_o=5\cdot 10^6\) and \(N_a=2.5\cdot 10^6\). The closed formulas implemented in C++, Python, and Java are all stated in terms of ordinary binomial coefficients \(\binom{n}{k}\) reduced modulo \(M\).
The code does not carry a recurrence over positions. Instead, the XO game has already been reduced to a parity classification of legal states. Denote by \(E_{\text{tot}}\) the number of even-parity states, by \(E_{\text{lost}}\) the number of even-parity states that are losing, and by \(O_{\text{win}}\) the number of odd-parity states that are winning. Then the required answer is
$$\boxed{\text{Ans}=E_{\text{tot}}-E_{\text{lost}}+O_{\text{win}} \pmod M.}$$
This identity is the structural backbone of the solution. Everything else is a closed-form evaluation of these three terms.
The first block is
$$E_{\text{tot}}=\sum_{m=0}^{N_o}\binom{N+2m-1}{2m}.$$
For a fixed \(m\), the coefficient \(\binom{N+2m-1}{2m}\) is the standard stars-and-bars count of weak compositions of \(2m\) into \(N\) slots. That is the reason the implementation never enumerates states individually: every even layer indexed by \(2m\) is counted in one shot, and the global total is just the sum over \(m=0,1,\dots,N/2\).
The upper index \(N+2m-1\) is also important computationally. Since \(m\le N/2\), the largest value that ever appears here is \(2N-1\), which explains why the implementations precompute factorial data up to \(2N\).
The losing part of the even layer is not a single uniform family. The formulas split it into one main sum and one separate boundary contribution:
$$L_1=\frac12\sum_{r=0}^{N_a}\binom{N_o}{2r}\binom{3N_o-r}{N_o-r},\qquad L_2=\frac12\binom{5N_a}{N_o},$$
$$E_{\text{lost}}=L_1+L_2.$$
The first factor \(\binom{N_o}{2r}\) selects an even-sized distinguished subset inside the half-sized parameter \(N_o\). After that choice is fixed, the second factor \(\binom{3N_o-r}{N_o-r}\) counts the remaining slack combinatorially. So each summand is a product of a parity-constrained choice term and a residual distribution term.
The extra term \(L_2\) shows that the even-loss classification has a special edge family that is not absorbed into the bulk sum. The factor \(1/2\) is not cosmetic: because the modulus is odd and prime, dividing by \(2\) is implemented as multiplication by the modular inverse of \(2\).
The odd layer contributes only through the winning states:
$$O_{\text{win}}=\frac12\sum_{r=0}^{N_a-1}\binom{N_o}{2r+1}\binom{3N_o-1-r}{N_o-1-r}.$$
This has the same flavor as the previous block, but now the selected subset size is odd, namely \(2r+1\). The second binomial coefficient shifts accordingly from \((3N_o-r,\ N_o-r)\) to \((3N_o-1-r,\ N_o-1-r)\). That shift is exactly what the implementations compute; it is the algebraic signature of passing from the even-loss family to the odd-win family.
The important point is that no recursion remains. By the time the code runs, the game theory has been compressed into a parity split and three one-dimensional sums.
Substituting the definitions gives the full formula used by the code:
$$\boxed{\text{Ans}=\sum_{m=0}^{N_o}\binom{N+2m-1}{2m}-\frac12\sum_{r=0}^{N_a}\binom{N_o}{2r}\binom{3N_o-r}{N_o-r}-\frac12\binom{5N_a}{N_o}+\frac12\sum_{r=0}^{N_a-1}\binom{N_o}{2r+1}\binom{3N_o-1-r}{N_o-1-r}\pmod M.}$$
For Problem 976 the heavy work is therefore arithmetic, not search. Once the binomial table is available, the answer is a direct modular accumulation.
A small case makes the structure concrete. If \(N=4\), then \(N_o=2\) and \(N_a=1\). The three blocks become
$$E_{\text{tot}}=\binom30+\binom52+\binom74=1+10+35=46,$$
$$L_1=\frac12\left(\binom20\binom62+\binom22\binom51\right)=\frac12(15+5)=10,$$
$$L_2=\frac12\binom52=5,$$
$$O_{\text{win}}=\frac12\left(\binom21\binom51\right)=5.$$
Hence
$$\text{Ans}=46-(10+5)+5=36.$$
This miniature example uses exactly the same decomposition as the full \(N=10^7\) computation; only the ranges of the sums change.
The implementations build factorial and inverse-factorial tables up to \(2N\). Because the modulus \(M=1234567891\) is prime, inverse factorials are obtained with Fermat's little theorem: \(a^{-1}\equiv a^{M-2}\pmod M\). After that preprocessing, every \(\binom{n}{k}\) needed by the three formulas is available in constant time.
The C++ implementation also performs a few sanity checks before the large summations begin: it verifies that factorial and inverse-factorial tables multiply back to \(1\), checks some trivial binomial identities, and confirms that the modular inverse of \(2\) behaves correctly.
The implementation then evaluates the three formula families exactly as written above. One loop runs over \(m=0,\dots,N_o\) for \(E_{\text{tot}}\), one loop runs over \(r=0,\dots,N_a\) for the raw part of \(L_1\), and a third loop runs over \(r=0,\dots,N_a-1\) for the raw part of \(O_{\text{win}}\). The separate boundary term \(L_2\) is a single binomial lookup. Finally, the answer is assembled as
$$E_{\text{tot}}-(L_1+L_2)+O_{\text{win}} \pmod M.$$
The arithmetic is identical in all three languages, but the execution strategy differs slightly. The C++ version slices the long sums into thread ranges manually, the Java version uses parallel streams for the same purpose, and the Python version keeps the loops serial. In every case, the mathematical content is identical: only the scheduling of additions changes.
The dominant preprocessing cost is the factorial table up to \(2N\), so both time and memory for that phase are \(O(N)\). Afterward, the three summations have lengths \(N_o+1\), \(N_a+1\), and \(N_a\), which is still linear in \(N\). There is no hidden quadratic step anywhere in the implementation.
Therefore the overall complexity is \(O(N)\) time and \(O(N)\) memory, with fairly small constant factors once the modular tables are available. For the actual target \(N=10^7\), memory is dominated by the factorial and inverse-factorial arrays, while the remaining state consists only of a few running modular sums.
Problem 976, XO Game, wird in den Implementierungen vollständig über kombinatorische Formeln modulo \(1234567891\) gelöst. Für den Zielwert \(N=10^7\) ist nur der Fall \(N\equiv 0 \pmod 4\) relevant. Deshalb braucht man weder eine Spielbaumsuche noch eine Simulation einzelner Partien; alles reduziert sich auf drei geschlossene Summen.
Die zentrale Invariante ist die Parität der Zustände. Der Endwert entsteht aus der Anzahl aller Zustände gerader Parität, korrigiert um die geraden Verlustzustände und ergänzt um die ungeraden Gewinnzustände. Genau diese Dreiteilung ist in allen drei Implementierungen sichtbar.
Wir schreiben
$$M=1234567891,\qquad N_o=\frac N2,\qquad N_a=\frac N4.$$
Für die konkrete Euler-Eingabe gilt also \(N_o=5\cdot 10^6\) und \(N_a=2{,}5\cdot 10^6\). Alle Beiträge werden mit gewöhnlichen Binomialkoeffizienten \(\binom{n}{k}\) beschrieben und anschließend modulo \(M\) ausgewertet.
Im fertigen Code bleibt keine Rekursion über Spielpositionen mehr übrig. Die Spielanalyse wurde bereits auf drei Klassen komprimiert: \(E_{\text{tot}}\) für alle Zustände gerader Parität, \(E_{\text{lost}}\) für gerade Verlustzustände und \(O_{\text{win}}\) für ungerade Gewinnzustände. Damit lautet die Zielformel
$$\boxed{\text{Ans}=E_{\text{tot}}-E_{\text{lost}}+O_{\text{win}} \pmod M.}$$
Diese Identität ist der eigentliche Kern der Methode. Die verbleibende Arbeit besteht nur noch darin, die drei Terme effizient zu zählen.
Der erste Block ist
$$E_{\text{tot}}=\sum_{m=0}^{N_o}\binom{N+2m-1}{2m}.$$
Für festes \(m\) ist \(\binom{N+2m-1}{2m}\) die klassische Stars-and-Bars-Zahl der schwachen Zerlegungen von \(2m\) in \(N\) Teile. Genau deshalb muss die Implementierung keine Zustände einzeln erzeugen: Jede gerade Schicht mit Parameter \(2m\) wird in einem Schritt gezählt, und die Gesamtsumme entsteht durch Summation über \(m=0,1,\dots,N/2\).
Auch rechnerisch ist die obere Grenze wichtig. Da \(m\le N/2\), ist \(N+2m-1\le 2N-1\). Deshalb reichen Fakultäts- und Inversfakultätstabellen bis \(2N\) aus.
Die geraden Verlustzustände zerfallen in einen Hauptanteil und einen zusätzlichen Randanteil:
$$L_1=\frac12\sum_{r=0}^{N_a}\binom{N_o}{2r}\binom{3N_o-r}{N_o-r},\qquad L_2=\frac12\binom{5N_a}{N_o},$$
$$E_{\text{lost}}=L_1+L_2.$$
Der Faktor \(\binom{N_o}{2r}\) wählt eine gerade Anzahl \(2r\) ausgezeichneter Elemente innerhalb der Halbgröße \(N_o\). Der zweite Faktor \(\binom{3N_o-r}{N_o-r}\) zählt anschließend die verbleibenden Freiheitsgrade kombinatorisch. Jeder Summand ist also das Produkt aus einer paritätsgebundenen Auswahl und einer Restverteilung.
Der Zusatzterm \(L_2\) zeigt, dass die geraden Verlustzustände noch eine eigene Randfamilie besitzen, die nicht in der Hauptsumme aufgeht. Die Division durch \(2\) wird im Modul nicht durch Fließkomma behandelt, sondern durch Multiplikation mit dem modularen Inversen von \(2\).
Von der ungeraden Schicht wird nur der Gewinnanteil addiert:
$$O_{\text{win}}=\frac12\sum_{r=0}^{N_a-1}\binom{N_o}{2r+1}\binom{3N_o-1-r}{N_o-1-r}.$$
Die Struktur ist der vorherigen Summe sehr ähnlich, nur dass nun eine ungerade Anzahl \(2r+1\) ausgewählt wird. Entsprechend verschiebt sich auch der zweite Binomialkoeffizient von \((3N_o-r,\ N_o-r)\) auf \((3N_o-1-r,\ N_o-1-r)\). Genau diese Verschiebung codiert den Übergang von der geraden Verlustfamilie zur ungeraden Gewinnfamilie.
Wichtig ist: In der Endformel gibt es kein dynamisches Programm mehr. Die gesamte Spieltheorie ist bereits in diese drei eindimensionalen Summen eingearbeitet.
Setzt man alle Definitionen ein, erhält man exakt die Formel, die die Implementierungen auswerten:
$$\boxed{\text{Ans}=\sum_{m=0}^{N_o}\binom{N+2m-1}{2m}-\frac12\sum_{r=0}^{N_a}\binom{N_o}{2r}\binom{3N_o-r}{N_o-r}-\frac12\binom{5N_a}{N_o}+\frac12\sum_{r=0}^{N_a-1}\binom{N_o}{2r+1}\binom{3N_o-1-r}{N_o-1-r}\pmod M.}$$
Für Problem 976 liegt die Schwierigkeit also nicht in der Zustandsdurchmusterung, sondern in einer großen, aber sauberen modularen Auswertung dieser Summen.
Ein sehr kleines Beispiel macht die Struktur sichtbar. Für \(N=4\) gilt \(N_o=2\) und \(N_a=1\). Dann erhält man
$$E_{\text{tot}}=\binom30+\binom52+\binom74=1+10+35=46,$$
$$L_1=\frac12\left(\binom20\binom62+\binom22\binom51\right)=\frac12(15+5)=10,$$
$$L_2=\frac12\binom52=5,$$
$$O_{\text{win}}=\frac12\left(\binom21\binom51\right)=5.$$
Daraus folgt
$$\text{Ans}=46-(10+5)+5=36.$$
Der Großfall \(N=10^7\) verwendet exakt dieselbe Zerlegung; nur die Summationsgrenzen werden riesig.
Alle Implementierungen bauen Fakultäts- und Inversfakultätstabellen bis \(2N\) auf. Weil \(M=1234567891\) eine Primzahl ist, lassen sich die inversen Fakultäten mit dem kleinen Satz von Fermat berechnen: \(a^{-1}\equiv a^{M-2}\pmod M\). Danach ist jeder benötigte Binomialkoeffizient ein \(O(1)\)-Lookup.
Die C++-Version führt zusätzlich einige Konsistenzprüfungen aus: Produkte aus Fakultät und Inversfakultät müssen \(1\) ergeben, einfache Identitäten \(\binom{n}{0}=\binom{n}{n}=1\) werden getestet, und auch das modulare Inverse von \(2\) wird kontrolliert.
Anschließend berechnet die Implementierung die drei Summenblöcke genau in der oben beschriebenen Form. Eine Schleife über \(m=0,\dots,N_o\) liefert \(E_{\text{tot}}\), eine Schleife über \(r=0,\dots,N_a\) den Rohwert für \(L_1\), und eine weitere Schleife über \(r=0,\dots,N_a-1\) den Rohwert für \(O_{\text{win}}\). Der Sonderterm \(L_2\) ist nur ein einzelner Binomialzugriff. Zum Schluss wird alles zu
$$E_{\text{tot}}-(L_1+L_2)+O_{\text{win}} \pmod M$$
zusammengesetzt.
Die Mathematik ist in allen drei Sprachen identisch, aber die Ausführung unterscheidet sich leicht. C++ teilt die langen Summen manuell auf Threads auf, Java verwendet dafür parallele Streams, und Python läuft seriell. In jedem Fall ändert sich nur die Abarbeitung, nicht die Formel.
Die Vorverarbeitung bis \(2N\) dominiert Speicher und Grundlaufzeit, also \(O(N)\) Zeit und \(O(N)\) Speicher. Danach haben die drei Summen die Längen \(N_o+1\), \(N_a+1\) und \(N_a\), insgesamt also weiterhin nur linearen Aufwand.
Damit ist die Gesamtlösung \(O(N)\) in der Zeit und \(O(N)\) im Speicher. Für \(N=10^7\) kommen die Hauptkosten fast vollständig von den Fakultätsarrays; daneben werden nur einige modulare Laufvariablen gehalten.
Problem 976, XO Game, çözümlerde tamamen kombinatorik sayım üzerinden ve \(1234567891\) modunda ele alınıyor. Hedef girdi \(N=10^7\) için gerekli tek durum \(N\equiv 0 \pmod 4\) olduğundan, herhangi bir oyun ağacı taraması, durum simülasyonu veya dinamik programlama yapılmıyor; her şey üç kapalı toplam formülüne indirgeniyor.
Üç uygulamanın da açıkça kullandığı ana değişmez paritedir. Sonuç, bütün çift-pariteli durumların sayısından çift-pariteli kayıp durumlarını çıkarıp tek-pariteli kazanım durumlarını ekleyerek kuruluyor. Kodun esas matematiksel omurgası tam olarak bu ayrımdır.
Şu notasyonu kullanalım:
$$M=1234567891,\qquad N_o=\frac N2,\qquad N_a=\frac N4.$$
Gerçek Euler girdisinde bunlar sırasıyla \(N_o=5\cdot 10^6\) ve \(N_a=2{,}5\cdot 10^6\) eder. Bütün kapalı ifadeler sıradan binom katsayıları \(\binom{n}{k}\) ile yazılıyor ve ardından \(M\) modunda hesaplanıyor.
Nihai koda bakıldığında artık herhangi bir özyineleme kalmadığı görülür. XO oyununun teorik analizi üç kümeye sıkıştırılmıştır: bütün çift-pariteli durumlar \(E_{\text{tot}}\), çift-pariteli kayıp durumları \(E_{\text{lost}}\) ve tek-pariteli kazanım durumları \(O_{\text{win}}\). Bu yüzden aranan değer
$$\boxed{\text{Ans}=E_{\text{tot}}-E_{\text{lost}}+O_{\text{win}} \pmod M}$$
şeklindedir. Çözümün geri kalan kısmı yalnızca bu üç terimi kapalı biçimde saymaktır.
İlk blok
$$E_{\text{tot}}=\sum_{m=0}^{N_o}\binom{N+2m-1}{2m}$$
olarak verilir. Sabit bir \(m\) için \(\binom{N+2m-1}{2m}\), \(2m\)'nin \(N\) yuvaya zayıf bileşimlerinin stars-and-bars sayımıdır. Dolayısıyla kod tek tek durum üretmek yerine, \(2m\) ile etiketlenen her çift katmanı doğrudan bir binom katsayısıyla sayabiliyor ve sonra \(m=0,1,\dots,N/2\) üzerinden topluyor.
Bu formül aynı zamanda neden faktöriyel tablolarının \(2N\)'e kadar kurulduğunu da açıklar. Çünkü \(m\le N/2\) olduğundan, burada görülen en büyük üst indeks \(N+2m-1\le 2N-1\) olur.
Çift katmandaki kayıp durumlar tek bir toplama sığmıyor; ana aile ve ayrı bir sınır terimi var:
$$L_1=\frac12\sum_{r=0}^{N_a}\binom{N_o}{2r}\binom{3N_o-r}{N_o-r},\qquad L_2=\frac12\binom{5N_a}{N_o},$$
$$E_{\text{lost}}=L_1+L_2.$$
Buradaki \(\binom{N_o}{2r}\) faktörü, \(N_o\) içinden çift sayıda \(2r\) özel seçim yapıldığını gösterir. Bu seçim sabitlenince geriye kalan serbestlik \(\binom{3N_o-r}{N_o-r}\) ile sayılır. Yani her terim, parite kısıtlı bir seçim çarpanı ile kalan dağıtım sayısının çarpımıdır.
Ayrı duran \(L_2\) terimi, çift kayıp sınıfında ana toplamın dışında kalan özel bir sınır ailesi olduğunu gösterir. Buradaki \(1/2\) gerçek bir modüler bölmedir; uygulamalar bunu 2'nin modüler tersiyle çarparak gerçekleştirir.
Tek katmandan yalnızca kazanım durumları eklenir:
$$O_{\text{win}}=\frac12\sum_{r=0}^{N_a-1}\binom{N_o}{2r+1}\binom{3N_o-1-r}{N_o-1-r}.$$
Bu toplamın yapısı bir öncekine çok benzer; ancak bu kez seçilen özel öğe sayısı çift değil tek, yani \(2r+1\)'dir. Buna paralel olarak ikinci binom katsayısı da \((3N_o-r,\ N_o-r)\) biçiminden \((3N_o-1-r,\ N_o-1-r)\) biçimine kayar. Kodun yaptığı hesap tam olarak bu kaymayı takip eder.
Önemli nokta şudur: Son ifadede artık bir durum-uzay özyinelemesi yoktur. Oyun kuramı kısmı tamamen parite ayrımına ve bu üç tek boyutlu toplama gömülmüştür.
Bütün parçaları yerine koyunca, uygulamaların hesapladığı tam ifade
$$\boxed{\text{Ans}=\sum_{m=0}^{N_o}\binom{N+2m-1}{2m}-\frac12\sum_{r=0}^{N_a}\binom{N_o}{2r}\binom{3N_o-r}{N_o-r}-\frac12\binom{5N_a}{N_o}+\frac12\sum_{r=0}^{N_a-1}\binom{N_o}{2r+1}\binom{3N_o-1-r}{N_o-1-r}\pmod M}$$
olur. Problem 976 için esas zorluk arama yapmak değil, bu büyük ama temiz kapalı toplamları modüler olarak değerlendirmektir.
Küçük bir örnek yapıyı netleştirir. \(N=4\) için \(N_o=2\) ve \(N_a=1\) olur. O zaman
$$E_{\text{tot}}=\binom30+\binom52+\binom74=1+10+35=46,$$
$$L_1=\frac12\left(\binom20\binom62+\binom22\binom51\right)=\frac12(15+5)=10,$$
$$L_2=\frac12\binom52=5,$$
$$O_{\text{win}}=\frac12\left(\binom21\binom51\right)=5.$$
Dolayısıyla
$$\text{Ans}=46-(10+5)+5=36.$$
Büyük hedef girdi \(N=10^7\) için de kullanılan mekanizma aynıdır; değişen tek şey toplam sınırlarının devasa olmasıdır.
Üç uygulama da önce \(2N\)'e kadar faktöriyel ve ters faktöriyel tabloları kurar. Modül \(M=1234567891\) asal olduğu için tersler Fermat'nın küçük teoremiyle hesaplanır: \(a^{-1}\equiv a^{M-2}\pmod M\). Böylece gerekli her \(\binom{n}{k}\) çağrısı sabit zamanda elde edilir.
C++ sürümü büyük toplamlar başlamadan önce birkaç tutarlılık kontrolü de yapar: faktöriyel ile ters faktöriyel çarpımının 1 verdiği doğrulanır, bazı temel binom özdeşlikleri test edilir ve 2'nin modüler tersinin doğru çalıştığı kontrol edilir.
Daha sonra uygulama yukarıdaki üç formül ailesini doğrudan hesaplar. \(m=0,\dots,N_o\) aralığı \(E_{\text{tot}}\) için dolaşılır, \(r=0,\dots,N_a\) aralığı \(L_1\)'in ham toplamını verir, \(r=0,\dots,N_a-1\) aralığı da \(O_{\text{win}}\)'in ham toplamını üretir. Ayrı duran \(L_2\) ise tek bir binom katsayısı değerlendirmesidir. Son adımda bütün katkılar
$$E_{\text{tot}}-(L_1+L_2)+O_{\text{win}} \pmod M$$
biçiminde birleştirilir.
Matematik her dilde aynıdır; sadece yürütme biçimi değişir. C++ uzun toplamları elle iş parçacıklarına böler, Java paralel akışlar kullanır, Python ise döngüleri seri çalıştırır. Sonucun değişmemesinin nedeni toplama ve mod alma işlemlerinin aynı cebirsel ifadeyi hesaplamasıdır.
Faktöriyel ön işleme aşaması \(2N\)'e kadar uzandığı için hem zaman hem bellek maliyeti \(O(N)\)'dir. Bundan sonra yapılan üç toplamın uzunlukları sırasıyla \(N_o+1\), \(N_a+1\) ve \(N_a\) olduğundan toplam ek maliyet yine doğrusaldır.
Dolayısıyla tüm çözüm \(O(N)\) zaman ve \(O(N)\) bellek kullanır. Gerçek hedef olan \(N=10^7\) için belleğin büyük kısmını faktöriyel ve ters faktöriyel dizileri kaplar; geri kalan durum birkaç modüler akümülatörden ibarettir.
El Problema 976, XO Game, se resuelve en las implementaciones mediante un conteo combinatorio puro módulo \(1234567891\). Para la entrada objetivo \(N=10^7\), solo hace falta el caso \(N\equiv 0 \pmod 4\). Por eso no aparece ninguna exploración del árbol de juego ni simulación explícita de estados: todo termina reducido a tres sumas cerradas.
La invariante central es la paridad. El resultado final se obtiene contando todos los estados de paridad par, restando los estados pares que son perdedores y sumando los estados impares que son ganadores. Esa descomposición es exactamente la que codifican las tres versiones del programa.
Usaremos la notación
$$M=1234567891,\qquad N_o=\frac N2,\qquad N_a=\frac N4.$$
En la instancia real de Project Euler esto significa \(N_o=5\cdot 10^6\) y \(N_a=2{,}5\cdot 10^6\). Todas las expresiones se escriben con coeficientes binomiales ordinarios \(\binom{n}{k}\) y después se reducen módulo \(M\).
En el código final ya no queda ninguna recurrencia sobre posiciones del juego. Todo se ha condensado en tres cantidades: \(E_{\text{tot}}\), el número total de estados de paridad par; \(E_{\text{lost}}\), los estados pares perdedores; y \(O_{\text{win}}\), los estados impares ganadores. Con eso, la respuesta buscada es
$$\boxed{\text{Ans}=E_{\text{tot}}-E_{\text{lost}}+O_{\text{win}} \pmod M.}$$
Esta identidad es la estructura conceptual de toda la solución. Lo demás es evaluar cada bloque en forma cerrada.
El primer bloque es
$$E_{\text{tot}}=\sum_{m=0}^{N_o}\binom{N+2m-1}{2m}.$$
Para un \(m\) fijo, \(\binom{N+2m-1}{2m}\) es el conteo clásico de estrellas y barras para composiciones débiles de \(2m\) en \(N\) casillas. Esa interpretación combinatoria explica por qué la implementación puede saltarse la enumeración explícita: cada capa par indexada por \(2m\) se cuenta de una sola vez, y el total sale al sumar \(m=0,1,\dots,N/2\).
También explica el tamaño de las tablas combinatorias. Como \(m\le N/2\), el mayor índice superior que aparece aquí es \(N+2m-1\le 2N-1\), así que precomputar factoriales hasta \(2N\) es suficiente.
La parte perdedora de la capa par se divide en una familia principal y una contribución de borde:
$$L_1=\frac12\sum_{r=0}^{N_a}\binom{N_o}{2r}\binom{3N_o-r}{N_o-r},\qquad L_2=\frac12\binom{5N_a}{N_o},$$
$$E_{\text{lost}}=L_1+L_2.$$
El factor \(\binom{N_o}{2r}\) selecciona un subconjunto distinguido de tamaño par \(2r\) dentro de \(N_o\) elementos posibles. Fijada esa elección, el segundo factor \(\binom{3N_o-r}{N_o-r}\) cuenta combinatoriamente la libertad restante. Así, cada sumando es el producto de un término de elección restringido por paridad y un término de distribución residual.
El término adicional \(L_2\) muestra que la clasificación de pérdidas pares tiene una familia extrema separada del bloque principal. El factor \(1/2\) se implementa multiplicando por el inverso modular de \(2\), no con aritmética real.
De la capa impar solo se añaden los estados ganadores:
$$O_{\text{win}}=\frac12\sum_{r=0}^{N_a-1}\binom{N_o}{2r+1}\binom{3N_o-1-r}{N_o-1-r}.$$
La forma es casi la misma que antes, pero ahora el tamaño seleccionado es impar, \(2r+1\). Por eso el segundo coeficiente binomial se desplaza de \((3N_o-r,\ N_o-r)\) a \((3N_o-1-r,\ N_o-1-r)\). Ese desplazamiento es exactamente el rasgo algebraico que distingue el bloque impar ganador del bloque par perdedor.
La idea esencial es que ya no queda ningún proceso iterativo sobre estados. Toda la teoría del juego ha sido absorbida por esta partición de paridad y por tres sumas unidimensionales.
Al reunir todas las piezas obtenemos la expresión completa usada por el código:
$$\boxed{\text{Ans}=\sum_{m=0}^{N_o}\binom{N+2m-1}{2m}-\frac12\sum_{r=0}^{N_a}\binom{N_o}{2r}\binom{3N_o-r}{N_o-r}-\frac12\binom{5N_a}{N_o}+\frac12\sum_{r=0}^{N_a-1}\binom{N_o}{2r+1}\binom{3N_o-1-r}{N_o-1-r}\pmod M.}$$
Así, para el Problema 976 el trabajo pesado es puramente aritmético: una vez construida la tabla de binomiales, la respuesta sale de una acumulación modular directa.
Un ejemplo pequeño aclara la estructura. Si \(N=4\), entonces \(N_o=2\) y \(N_a=1\). Los bloques valen
$$E_{\text{tot}}=\binom30+\binom52+\binom74=1+10+35=46,$$
$$L_1=\frac12\left(\binom20\binom62+\binom22\binom51\right)=\frac12(15+5)=10,$$
$$L_2=\frac12\binom52=5,$$
$$O_{\text{win}}=\frac12\left(\binom21\binom51\right)=5.$$
Por lo tanto,
$$\text{Ans}=46-(10+5)+5=36.$$
El caso real \(N=10^7\) usa exactamente la misma descomposición; solo cambian los límites de las sumas.
Las implementaciones construyen tablas de factoriales e inversos factoriales hasta \(2N\). Como \(M=1234567891\) es primo, los inversos se obtienen con el pequeño teorema de Fermat: \(a^{-1}\equiv a^{M-2}\pmod M\). Después de ese preproceso, cada \(\binom{n}{k}\) necesario se consulta en tiempo constante.
La versión en C++ además ejecuta algunas comprobaciones de consistencia antes de empezar las sumas grandes: verifica que factorial e inverso factorial se cancelan correctamente, revisa identidades binomiales básicas y confirma que el inverso modular de \(2\) es correcto.
Luego el programa evalúa literalmente las tres familias de sumas. Un bucle sobre \(m=0,\dots,N_o\) acumula \(E_{\text{tot}}\), otro sobre \(r=0,\dots,N_a\) acumula la parte bruta de \(L_1\), y un tercero sobre \(r=0,\dots,N_a-1\) acumula la parte bruta de \(O_{\text{win}}\). El término especial \(L_2\) es una sola consulta binomial. Al final todo se combina como
$$E_{\text{tot}}-(L_1+L_2)+O_{\text{win}} \pmod M.$$
La matemática es la misma en C++, Python y Java, pero la planificación cambia. C++ divide manualmente los rangos de suma entre varios hilos, Java usa streams paralelos y Python mantiene la versión serial. La expresión algebraica evaluada es idéntica en los tres casos.
El coste dominante de preproceso es la construcción de las tablas hasta \(2N\), así que esa fase usa \(O(N)\) tiempo y \(O(N)\) memoria. Después, las tres sumas tienen longitudes \(N_o+1\), \(N_a+1\) y \(N_a\), que en conjunto siguen siendo lineales en \(N\).
En consecuencia, la solución completa es \(O(N)\) en tiempo y \(O(N)\) en memoria. Para \(N=10^7\), la memoria está dominada por los arreglos de factoriales e inversos factoriales; fuera de eso, el programa solo mantiene unas pocas sumas modulares acumuladas.
第 976 题 XO Game 在实现中不是通过枚举对局、搜索博弈树或做状态模拟来求解，而是直接在模 \(1234567891\) 下计算三个封闭的组合和。对于目标输入 \(N=10^7\)，程序只处理 \(N\equiv 0 \pmod 4\) 的情形，因此整个问题被压缩成一个纯粹的计数问题。
三份实现共享的核心不变量是“奇偶层”的划分。最终答案由三部分组成：所有偶奇偶状态的总数、其中属于必败的偶状态，以及属于必赢的奇状态。换句话说，程序先数完整个偶层，再减去偶层中的失败部分，最后加回奇层中的成功部分。
记
$$M=1234567891,\qquad N_o=\frac N2,\qquad N_a=\frac N4.$$
对实际的 Project Euler 输入，\(N_o=5\cdot 10^6\)，\(N_a=2.5\cdot 10^6\)。代码中所有公式都用普通二项式系数 \(\binom{n}{k}\) 表示，然后在模 \(M\) 下计算。
最终实现里已经没有递推式或状态转移表。关于 XO Game 的博弈分析在代码层面只留下三个数量：偶层状态总数 \(E_{\text{tot}}\)、偶层中的必败状态数 \(E_{\text{lost}}\)、奇层中的必赢状态数 \(O_{\text{win}}\)。因此答案直接写成
$$\boxed{\text{Ans}=E_{\text{tot}}-E_{\text{lost}}+O_{\text{win}} \pmod M.}$$
这就是整套做法的主线。后面的工作不再是“分析如何走棋”，而是“把这三个数量精确地数出来”。
第一块求和是
$$E_{\text{tot}}=\sum_{m=0}^{N_o}\binom{N+2m-1}{2m}.$$
对固定的 \(m\)，\(\binom{N+2m-1}{2m}\) 可以看成经典的 stars-and-bars 计数，也就是把 \(2m\) 分配到 \(N\) 个槽位中的弱组合数。这个解释很重要，因为它说明程序为什么完全不需要逐个生成状态：每一个由 \(2m\) 标记的偶层都能通过一个二项式系数一次性算完，然后再把 \(m=0,1,\dots,N/2\) 的结果累加。
这个式子还解释了为什么阶乘表只需要做到 \(2N\)。因为 \(m\le N/2\)，所以这里出现的最大上标满足 \(N+2m-1\le 2N-1\)。因此把组合数预处理到 \(2N\) 就已经覆盖了全部访问范围。
偶层中的失败部分并不是一个单一族，而是由一个主体求和和一个边界项组成：
$$L_1=\frac12\sum_{r=0}^{N_a}\binom{N_o}{2r}\binom{3N_o-r}{N_o-r},\qquad L_2=\frac12\binom{5N_a}{N_o},$$
$$E_{\text{lost}}=L_1+L_2.$$
其中 \(\binom{N_o}{2r}\) 表示在规模为 \(N_o\) 的对象中选出一个大小为偶数 \(2r\) 的特殊子集；在这一步固定之后，剩余自由度由 \(\binom{3N_o-r}{N_o-r}\) 负责计数。因此每一项都可以理解为“满足奇偶限制的选择”乘以“剩余部分的分配数”。
额外的 \(L_2\) 说明偶层必败状态里还有一个不能并入主体求和的边界家族。外面的 \(1/2\) 不是形式上的写法，而是真正的模运算除以 2；实现中用的是 \(2\) 在模 \(M\) 下的乘法逆元。
奇层只贡献其中的必赢部分：
$$O_{\text{win}}=\frac12\sum_{r=0}^{N_a-1}\binom{N_o}{2r+1}\binom{3N_o-1-r}{N_o-1-r}.$$
它的结构与上一块非常接近，但这里挑选的特殊数量变成了奇数 \(2r+1\)。正因为这一点，第二个二项式系数也从 \((3N_o-r,\ N_o-r)\) 平移到了 \((3N_o-1-r,\ N_o-1-r)\)。这种平移正是代码中区分“偶层必败”和“奇层必赢”的代数特征。
值得强调的是，程序在这里并没有做任何递推。真正留下来的只是奇偶分层后的三个一维求和公式。
把三块全部代入，可以得到实现中真正计算的总公式：
$$\boxed{\text{Ans}=\sum_{m=0}^{N_o}\binom{N+2m-1}{2m}-\frac12\sum_{r=0}^{N_a}\binom{N_o}{2r}\binom{3N_o-r}{N_o-r}-\frac12\binom{5N_a}{N_o}+\frac12\sum_{r=0}^{N_a-1}\binom{N_o}{2r+1}\binom{3N_o-1-r}{N_o-1-r}\pmod M.}$$
所以对第 976 题来说，真正困难的部分不是搜索，而是如何把这几个大规模组合和高效地模素数计算出来。
用一个小例子可以把结构看得更清楚。若 \(N=4\)，则 \(N_o=2\)，\(N_a=1\)。于是
$$E_{\text{tot}}=\binom30+\binom52+\binom74=1+10+35=46,$$
$$L_1=\frac12\left(\binom20\binom62+\binom22\binom51\right)=\frac12(15+5)=10,$$
$$L_2=\frac12\binom52=5,$$
$$O_{\text{win}}=\frac12\left(\binom21\binom51\right)=5.$$
因此
$$\text{Ans}=46-(10+5)+5=36.$$
实际题目中的 \(N=10^7\) 与这个例子在结构上完全相同，只是求和范围大得多。
C++、Python 和 Java 三份实现都会先预处理到 \(2N\) 为止的阶乘与逆阶乘表。因为模数 \(M=1234567891\) 是素数，所以逆元可以用费马小定理计算：\(a^{-1}\equiv a^{M-2}\pmod M\)。一旦这些表建好，后续每个 \(\binom{n}{k}\) 都是 \(O(1)\) 查询。
C++ 版本在正式进入大规模求和前还做了几项一致性检查，例如验证阶乘和逆阶乘相乘是否回到 \(1\)，检查若干平凡的组合恒等式，以及确认 \(2\) 的模逆确实正确。
之后程序就按公式本身来做。第一重循环遍历 \(m=0,\dots,N_o\) 以累加 \(E_{\text{tot}}\)；第二重循环遍历 \(r=0,\dots,N_a\) 以计算 \(L_1\) 的原始和；第三重循环遍历 \(r=0,\dots,N_a-1\) 以计算 \(O_{\text{win}}\) 的原始和。单独的 \(L_2\) 只是一次二项式查询。最终答案按
$$E_{\text{tot}}-(L_1+L_2)+O_{\text{win}} \pmod M$$
组合起来。
三种语言的数学完全一致，但执行方式略有不同。C++ 手动把长区间拆给多个线程，Java 使用并行流，Python 则保持串行循环。无论采用哪一种调度方式，计算的都是同一个模意义下的闭式表达式。
最主要的预处理成本来自长度为 \(2N\) 的阶乘和逆阶乘表，因此这一阶段需要 \(O(N)\) 时间和 \(O(N)\) 空间。之后三段求和的长度分别是 \(N_o+1\)、\(N_a+1\) 和 \(N_a\)，总量仍然只是线性的。
所以整个算法的总复杂度是 \(O(N)\) 时间、\(O(N)\) 空间。对目标输入 \(N=10^7\) 来说，内存几乎都耗在组合数表上，其余部分只保存少量模和与循环变量。
Задача 976, XO Game, в реализациях решается не через перебор партий и не через динамику по игровым состояниям, а через прямое вычисление трёх замкнутых комбинаторных сумм по модулю \(1234567891\). Для целевого значения \(N=10^7\) нужен только случай \(N\equiv 0 \pmod 4\), поэтому вся логика сводится к чистой арифметике биномиальных коэффициентов.
Главная инварианта, которая явно видна в коде, это чётность состояния. Окончательный ответ строится как число всех состояний чётной парности, из которого вычитаются проигрышные чётные состояния, а затем добавляются выигрышные нечётные состояния. Именно такая трёхчастная структура и реализована во всех трёх языках.
Введём обозначения
$$M=1234567891,\qquad N_o=\frac N2,\qquad N_a=\frac N4.$$
Для фактического входа Project Euler это даёт \(N_o=5\cdot 10^6\) и \(N_a=2{,}5\cdot 10^6\). Все формулы ниже записываются через обычные биномиальные коэффициенты \(\binom{n}{k}\) и затем вычисляются по модулю \(M\).
В итоговой программе уже не осталось никакой рекурсии по позициям игры. Вся предварительная теория сведена к трём величинам: \(E_{\text{tot}}\) — число всех состояний чётной парности, \(E_{\text{lost}}\) — число проигрышных состояний среди них, и \(O_{\text{win}}\) — число выигрышных состояний нечётной парности. Поэтому искомая величина имеет вид
$$\boxed{\text{Ans}=E_{\text{tot}}-E_{\text{lost}}+O_{\text{win}} \pmod M.}$$
Это и есть основная математическая идея решения. Дальше остаётся только вычислить каждый блок в замкнутом виде.
Первый блок задаётся формулой
$$E_{\text{tot}}=\sum_{m=0}^{N_o}\binom{N+2m-1}{2m}.$$
Для фиксированного \(m\) коэффициент \(\binom{N+2m-1}{2m}\) является стандартным числом stars-and-bars, то есть количеством слабых разбиений числа \(2m\) на \(N\) ячеек. Именно поэтому программа не перечисляет состояния по одному: каждый чётный слой с параметром \(2m\) считается сразу, а потом все такие слои суммируются по \(m=0,1,\dots,N/2\).
Из этой же формулы видно, почему таблиц факториалов до \(2N\) достаточно. Так как \(m\le N/2\), максимальный верхний индекс здесь равен \(N+2m-1\le 2N-1\).
Проигрышная часть чётного слоя распадается на основной суммарный блок и отдельный граничный вклад:
$$L_1=\frac12\sum_{r=0}^{N_a}\binom{N_o}{2r}\binom{3N_o-r}{N_o-r},\qquad L_2=\frac12\binom{5N_a}{N_o},$$
$$E_{\text{lost}}=L_1+L_2.$$
Множитель \(\binom{N_o}{2r}\) выбирает специальное подмножество чётного размера \(2r\) среди \(N_o\) объектов. После фиксации этого выбора оставшаяся свобода кодируется коэффициентом \(\binom{3N_o-r}{N_o-r}\). Поэтому каждый член суммы естественно читать как произведение «чётностного выбора» и «остаточного распределения».
Дополнительный член \(L_2\) показывает, что в классе чётных проигрышей есть особая крайняя семья, которая не поглощается основной суммой. Деление на \(2\) в модульной арифметике реализуется умножением на обратный элемент к \(2\).
От нечётного слоя нужен только выигрышный вклад:
$$O_{\text{win}}=\frac12\sum_{r=0}^{N_a-1}\binom{N_o}{2r+1}\binom{3N_o-1-r}{N_o-1-r}.$$
Структура почти та же самая, но теперь размер специального множества нечётный и равен \(2r+1\). Из-за этого второй биномиальный коэффициент сдвигается с \((3N_o-r,\ N_o-r)\) на \((3N_o-1-r,\ N_o-1-r)\). Именно этот сдвиг и является алгебраическим отличием нечётного выигрышного блока от чётного проигрышного.
С точки зрения реализации важно, что никакой динамики уже не осталось: вся теория игры свернулась в три одномерные суммы.
Подставляя все определения, получаем точную формулу, которую вычисляет код:
$$\boxed{\text{Ans}=\sum_{m=0}^{N_o}\binom{N+2m-1}{2m}-\frac12\sum_{r=0}^{N_a}\binom{N_o}{2r}\binom{3N_o-r}{N_o-r}-\frac12\binom{5N_a}{N_o}+\frac12\sum_{r=0}^{N_a-1}\binom{N_o}{2r+1}\binom{3N_o-1-r}{N_o-1-r}\pmod M.}$$
Таким образом, для задачи 976 основная тяжесть лежит не в переборе, а в быстром модульном вычислении больших комбинаторных сумм.
Маленький пример делает структуру более наглядной. При \(N=4\) имеем \(N_o=2\) и \(N_a=1\). Тогда
$$E_{\text{tot}}=\binom30+\binom52+\binom74=1+10+35=46,$$
$$L_1=\frac12\left(\binom20\binom62+\binom22\binom51\right)=\frac12(15+5)=10,$$
$$L_2=\frac12\binom52=5,$$
$$O_{\text{win}}=\frac12\left(\binom21\binom51\right)=5.$$
Следовательно,
$$\text{Ans}=46-(10+5)+5=36.$$
Для настоящего входа \(N=10^7\) используется та же самая схема; меняются только пределы сумм.
Во всех трёх реализациях заранее строятся таблицы факториалов и обратных факториалов до \(2N\). Поскольку модуль \(M=1234567891\) прост, обратные элементы находятся по малой теореме Ферма: \(a^{-1}\equiv a^{M-2}\pmod M\). После этого любой нужный \(\binom{n}{k}\) получается за \(O(1)\).
Реализация на C++ дополнительно запускает несколько проверок согласованности: убеждается, что факториал и обратный факториал взаимно сокращаются, проверяет простые тождества \(\binom{n}{0}=\binom{n}{n}=1\) и отдельно тестирует корректность обратного элемента к \(2\).
Дальше код буквально проходит по формулам. Цикл по \(m=0,\dots,N_o\) даёт \(E_{\text{tot}}\), цикл по \(r=0,\dots,N_a\) даёт сырой вклад для \(L_1\), а цикл по \(r=0,\dots,N_a-1\) — сырой вклад для \(O_{\text{win}}\). Отдельный член \(L_2\) получается одной биномиальной выборкой. Затем всё собирается как
$$E_{\text{tot}}-(L_1+L_2)+O_{\text{win}} \pmod M.$$
Математика во всех языках одинакова, но способ выполнения немного различается. В C++ большие диапазоны сумм разбиваются между потоками вручную, в Java для этого используются parallel streams, а Python оставляет циклы последовательными. Вычисляемая формула во всех случаях одна и та же.
Главный этап предобработки — построение таблиц длины \(2N\), поэтому он требует \(O(N)\) времени и \(O(N)\) памяти. После этого длины трёх сумм равны \(N_o+1\), \(N_a+1\) и \(N_a\), то есть суммарно это тоже линейный объём работы.
Итак, общая сложность решения составляет \(O(N)\) по времени и \(O(N)\) по памяти. Для входа \(N=10^7\) основной объём памяти занимают массивы факториалов и обратных факториалов; кроме них нужны лишь несколько накопительных переменных по модулю.
المسألة 976، XO Game، تُحل في هذه التطبيقات عن طريق عدٍّ توافقي مباشر modulo \(1234567891\)، لا عن طريق استكشاف شجرة اللعب ولا بمحاكاة جميع الحالات. وبما أن قيمة الإدخال المستهدفة هي \(N=10^7\) وأن الحل الفعلي يتعامل فقط مع الحالة \(N\equiv 0 \pmod 4\)، فإن المسألة تنضغط إلى ثلاث مجاميع مغلقة فقط.
الثابت الأهم الذي يظهر في الشيفرة هو ثنائية الفردي والزوجي. فالجواب النهائي يُبنى من عدد الحالات ذات parity الزوجية كلها، ثم يُطرح منها ما كان خاسراً داخل هذه الطبقة الزوجية، ثم يُضاف ما كان رابحاً داخل الطبقة الفردية. هذا هو الهيكل الرياضي الذي تتفق عليه تطبيقات ++C وPython وJava.
لنكتب
$$M=1234567891,\qquad N_o=\frac N2,\qquad N_a=\frac N4.$$
في الإدخال الحقيقي لمسألة Project Euler نحصل على \(N_o=5\cdot 10^6\) و\(N_a=2.5\cdot 10^6\). جميع الصيغ المكتوبة في الحل تعتمد على معاملات ثنائية \(\binom{n}{k}\) ثم تُختزل modulo \(M\).
لا يبقى في التنفيذ النهائي أي recurrence على حالات اللعبة. كل التحليل النظري للعبة XO قد اختُصر إلى ثلاث كميات: \(E_{\text{tot}}\) لعدد الحالات الزوجية كلها، و\(E_{\text{lost}}\) لعدد الحالات الزوجية الخاسرة، و\(O_{\text{win}}\) لعدد الحالات الفردية الرابحة. ومن ثم يكون الجواب
$$\boxed{\text{Ans}=E_{\text{tot}}-E_{\text{lost}}+O_{\text{win}} \pmod M.}$$
هذه المعادلة هي العمود الفقري للحل. وما بعد ذلك ليس إلا حساباً مغلقاً لكل حد من هذه الحدود الثلاثة.
الكتلة الأولى هي
$$E_{\text{tot}}=\sum_{m=0}^{N_o}\binom{N+2m-1}{2m}.$$
عند تثبيت \(m\)، فإن \(\binom{N+2m-1}{2m}\) هو عدّ stars-and-bars المعتاد، أي عدد التركيبات الضعيفة للعدد \(2m\) على \(N\) خانات. وهذا يفسر لماذا لا يحتاج البرنامج إلى توليد الحالات واحدة واحدة: كل طبقة زوجية مرتبطة بالقيمة \(2m\) تُحصى مباشرةً بمعامل ثنائي واحد، ثم تُجمع القيم على \(m=0,1,\dots,N/2\).
كما توضح هذه الصيغة سبب الاكتفاء بتهيئة الجداول حتى \(2N\). لأن \(m\le N/2\)، فإن أكبر فهرس علوي يظهر هنا هو \(N+2m-1\le 2N-1\).
الجزء الخاسر من الطبقة الزوجية لا يأتي في مجموع واحد فقط، بل ينقسم إلى كتلة رئيسية وحدّ طرفي مستقل:
$$L_1=\frac12\sum_{r=0}^{N_a}\binom{N_o}{2r}\binom{3N_o-r}{N_o-r},\qquad L_2=\frac12\binom{5N_a}{N_o},$$
$$E_{\text{lost}}=L_1+L_2.$$
العامل \(\binom{N_o}{2r}\) يختار مجموعة مميزة ذات حجم زوجي \(2r\) من بين \(N_o\) عناصر ممكنة. وبعد تثبيت هذا الاختيار، يأتي العامل الثاني \(\binom{3N_o-r}{N_o-r}\) ليعدّ ما تبقى من درجات الحرية. لذلك يمكن فهم كل حد في هذا المجموع على أنه حاصل ضرب اختيار مقيّد بالزوجية في عددٍ توافقي لتوزيع الجزء الباقي.
أما الحد الإضافي \(L_2\) فيبيّن أن فئة الخسارة الزوجية تحتوي أيضاً على عائلة حدّية لا تندمج داخل المجموع الرئيسي. والضرب في \(1/2\) يُنفَّذ حسابياً باستعمال المعكوس الضربي للعدد \(2\) modulo \(M\).
من الطبقة الفردية نحتاج فقط إلى الحالات الرابحة:
$$O_{\text{win}}=\frac12\sum_{r=0}^{N_a-1}\binom{N_o}{2r+1}\binom{3N_o-1-r}{N_o-1-r}.$$
البنية هنا شبيهة جداً بالكتلة السابقة، لكن عدد العناصر المميزة المختارة صار فردياً، أي \(2r+1\). ولهذا السبب ينتقل المعامل الثنائي الثاني من \((3N_o-r,\ N_o-r)\) إلى \((3N_o-1-r,\ N_o-1-r)\). هذا الانتقال هو العلامة الجبرية التي تميز فئة الربح الفردية عن فئة الخسارة الزوجية.
النقطة المهمة هي أن الشيفرة لا تنفذ أي recurrence بعد هذه المرحلة. فكل ما تبقى هو ثلاث مجاميع أحادية البعد ناتجة عن تفكيك parity.
بعد جمع القطع الثلاث نحصل على الصيغة الكاملة التي تحسبها التطبيقات:
$$\boxed{\text{Ans}=\sum_{m=0}^{N_o}\binom{N+2m-1}{2m}-\frac12\sum_{r=0}^{N_a}\binom{N_o}{2r}\binom{3N_o-r}{N_o-r}-\frac12\binom{5N_a}{N_o}+\frac12\sum_{r=0}^{N_a-1}\binom{N_o}{2r+1}\binom{3N_o-1-r}{N_o-1-r}\pmod M.}$$
إذن الصعوبة في Problem 976 ليست في البحث داخل فضاء الحالات، بل في تقييم هذه المجاميع التوافقية الكبيرة بسرعة ضمن حساب modulo أولي.
يفيد مثال صغير في توضيح البنية. إذا كان \(N=4\)، فحينها \(N_o=2\) و\(N_a=1\). تصبح الكتل الثلاث
$$E_{\text{tot}}=\binom30+\binom52+\binom74=1+10+35=46,$$
$$L_1=\frac12\left(\binom20\binom62+\binom22\binom51\right)=\frac12(15+5)=10,$$
$$L_2=\frac12\binom52=5,$$
$$O_{\text{win}}=\frac12\left(\binom21\binom51\right)=5.$$
ومن ثم
$$\text{Ans}=46-(10+5)+5=36.$$
الحالة الفعلية \(N=10^7\) تستعمل التفكيك نفسه تماماً؛ الذي يتغير فقط هو مدى المجاميع.
تقوم التطبيقات الثلاثة أولاً ببناء جداول المضروبات ومعكوسات المضروبات حتى \(2N\). وبما أن \(M=1234567891\) عدد أولي، فإن المعكوسات تُستخرج من مبرهنة فيرما الصغرى بالشكل \(a^{-1}\equiv a^{M-2}\pmod M\). بعد هذه التهيئة يصبح حساب أي \(\binom{n}{k}\) مطلوب عملية ثابتة الزمن.
نسخة ++C تضيف أيضاً عدداً من فحوص الاتساق قبل بدء المجاميع الكبيرة: فهي تتحقق من أن المضروب ومعكوسه يعودان إلى \(1\)، وتراجع بعض الهويات الثنائية البسيطة، وتؤكد صحة معكوس العدد \(2\) modulo \(M\).
بعد ذلك تُحسب المجاميع كما هي مكتوبة في الصيغ. توجد حلقة على \(m=0,\dots,N_o\) لحساب \(E_{\text{tot}}\)، وحلقة على \(r=0,\dots,N_a\) لحساب الجزء الخام من \(L_1\)، وحلقة ثالثة على \(r=0,\dots,N_a-1\) لحساب الجزء الخام من \(O_{\text{win}}\). أما \(L_2\) فهو مجرد استدعاء واحد لمعامل ثنائي. وفي النهاية تُجمَّع النتيجة على الصورة
$$E_{\text{tot}}-(L_1+L_2)+O_{\text{win}} \pmod M.$$
المحتوى الرياضي واحد في اللغات الثلاث، لكن أسلوب التنفيذ يختلف قليلاً. نسخة ++C تقسّم المجاميع الطويلة يدوياً على عدة خيوط، ونسخة Java تستخدم parallel streams، أما Python فتبقي الحلقات متسلسلة. في جميع الحالات تبقى الصيغة الجبرية نفسها دون تغيير.
الكلفة الأساسية في مرحلة التهيئة هي بناء الجداول حتى \(2N\)، ولهذا تكون كلفة الزمن والذاكرة \(O(N)\). وبعد ذلك فإن أطوال المجاميع الثلاثة هي \(N_o+1\) و\(N_a+1\) و\(N_a\)، أي أنها تبقى خطية في \(N\).
لذلك فالتعقيد الكلي للحل هو \(O(N)\) زمناً و\(O(N)\) ذاكرة. وعند \(N=10^7\) تكون الذاكرة مستهلكة أساساً في جداول المضروبات ومعكوساتها، بينما لا تحتاج بقية الخوارزمية إلا إلى عدد صغير من المجاميع الجارية modulo \(M\).