The target quantity is \(R(8,64)\) modulo \(10^9+7\). The implementations do not explore full Young positions cell by cell. Instead, they rely on the decomposition used by the game: a position splits into \(m\) independent diagonal components, and one component is encoded by positive integers \(a\) and \(b\) together with a nimber \(g\), subject to
$$a\ge 1,\qquad b\ge 1,\qquad 0\le g\le w-a-b-1.$$
Such a component contributes a game value of the form
$$d+\ast g,\qquad d=b-a.$$
For an \(m\)-component position, the integer parts add normally and the nimber parts combine by xor. So the whole position is controlled by two global invariants:
$$D=\sum_{i=1}^m d_i,\qquad X=g_1\oplus g_2\oplus \cdots \oplus g_m.$$
The implementations count exactly the states satisfying the final criterion \(D>0\), or \(D=0\) with \(X\ne 0\). Once that reduction is recognized, the problem becomes a counting problem over \((D,X)\) rather than a direct search over Young diagrams.
The derivation has two stages. First we catalogue every possible contribution of a single diagonal component. Then we combine \(m\) such components with a dynamic program that uses ordinary addition in the signed-difference coordinate and xor in the nimber coordinate.
Fix \(w\). The solution code explicitly enumerates all triples \((a,b,g)\) satisfying the admissibility conditions above. If we rewrite \(g+1=h\), then \(h\ge 1\) and
$$a+b+h\le w.$$
So the total number of local triples is
$$\sum_{a=1}^{w-2}\sum_{b=1}^{w-a-1}(w-a-b)=\binom{w}{3}.$$
For the target width \(w=64\), this local catalogue has \(\binom{64}{3}=41664\) entries. The important point is that the global computation does not need to remember the full triple. Only the signed difference \(d=b-a\) and the nimber \(g\) survive into later stages.
Many different pairs \((a,b)\) can produce the same local value \(d+\ast g\). The implementations therefore build a multiplicity table
$$C_w(d,g)=\#\left\{(a,b)\in\mathbb Z_{>0}^2:\ b-a=d,\ a+b+g\le w-1\right\}.$$
Every admissible triple contributes 1 to exactly one entry of this table. If we set \(u=w-g-1\), then the constraints become \(b-a=d\) and \(a+b\le u\). Solving them gives the closed form
$$C_w(d,g)=\max\left(0,\left\lfloor\frac{w-g-1-|d|}{2}\right\rfloor\right).$$
This explains several features of the code at once. The distribution is symmetric in \(d\), the support is finite, and the largest possible nimber is \(w-3\). For the target case \(w=64\), that means \(g\in\{0,1,\dots,61\}\), so a 64-state xor dimension is enough.
Let \(P_t(D,X)\) be the number of ways to choose \(t\) components whose total integer part is \(D\) and whose total nimber is \(X\). The empty choice gives the initial state
$$P_0(0,0)=1,$$
and every other state is zero at \(t=0\). When a new component with local value \(\delta+\ast g\) is appended, its integer part adds and its nimber xors, so the exact recurrence is
$$P_{t+1}(D,X)=\sum_{\delta}\sum_g P_t(D-\delta,\ X\oplus g)\,C_w(\delta,g).$$
This is the central formula of the solution. It replaces a huge space of board positions by a compact state space indexed only by a signed sum and an xor value.
After \(m\) rounds, we do not sum every state. The final selection rule used by the implementations is direct in this representation: keep every state with positive integer part, and from the row \(D=0\) keep only the nonzero xor states. Therefore
$$R(m,w)=\sum_{D>0}\sum_X P_m(D,X)+\sum_{X\ne 0} P_m(0,X).$$
The unique state \((D,X)=(0,0)\) is the exact zero value and must be excluded. In the code, this is implemented by summing every row with \(D>0\) completely and, for the single row \(D=0\), subtracting the entry at xor state 0.
The slow part of the recurrence is the xor-convolution over \(X\). A direct implementation would compare every previous xor state with every new xor state. Instead, the implementations apply the XOR Walsh-Hadamard transform to every row in the xor dimension. After that transform, xor-convolution becomes pointwise multiplication in frequency space:
$$\widehat{P}_{t+1}(D,\omega)=\sum_{\delta}\widehat{P}_t(D-\delta,\omega)\,\widehat{C}_w(\delta,\omega).$$
Now each frequency \(\omega\) can be processed independently, and the only remaining convolution is the ordinary one along the signed-sum axis. This is why the code first transforms the local table, then transforms the current dynamic-programming table at each round, performs one ordinary convolution per frequency, and finally applies the inverse transform.
When \(w=4\), the admissible triples are
$$ (a,b,g)\in\{(1,1,0),(1,1,1),(1,2,0),(2,1,0)\}. $$
So the only local values are
$$0,\qquad \ast 1,\qquad 1,\qquad -1.$$
Equivalently, the only nonzero local counts are
$$C_4(0,0)=1,\qquad C_4(0,1)=1,\qquad C_4(1,0)=1,\qquad C_4(-1,0)=1.$$
For \(m=2\), we form ordered pairs of these four local values and keep only totals with \(D>0\), or with \(D=0\) and nonzero nimber. The counted pairs are
$$ (1,1),\ (1,0),\ (0,1),\ (1,\ast 1),\ (\ast 1,1),\ (0,\ast 1),\ (\ast 1,0). $$
There are exactly 7 such pairs, matching the small checkpoint used by the implementations. This tiny case shows the whole method in miniature: build the local catalogue, combine components through \((D,X)\), and apply the final positivity rule.
The C++, Python, and Java implementations first enumerate all admissible triples \((a,b,g)\) and accumulate their multiplicities in the table \(C_w(d,g)\). To keep array indexing simple, they reserve a slightly wider signed-difference range than the mathematical support really needs. The same idea is used later for the global signed-sum axis, so every possible total \(D\) can be stored with a fixed offset.
The current state distribution starts from the single empty state \((D,X)=(0,0)\). At each of the \(m\) rounds, every xor row is transformed, the transformed local table is convolved with the transformed state table independently for each of the 64 frequencies, and then an inverse Walsh-Hadamard transform brings the result back to xor space. The recurrence is identical in all three languages. The C++ implementation additionally parallelizes the independent frequency loops, but the mathematics is unchanged.
After the last round, each row corresponds to one possible total \(D\). Summing across that row gives \(\sum_X P_m(D,X)\). Rows with positive \(D\) are added in full. For the unique row \(D=0\), the entry with xor value 0 is removed. That exactly implements the formula for \(R(m,w)\) above.
Building the local catalogue costs \(O(w^3)\) time, because the admissible triples \((a,b,g)\) are enumerated explicitly. The transformed dynamic program uses a local difference table with \(2w-3\) allocated rows and a global signed-sum table with \(2m(w-2)+1\) allocated rows, each with 64 xor entries.
In each of the \(m\) rounds, the algorithm performs Walsh-Hadamard transforms on all global rows and then runs 64 ordinary convolutions against the local table. This gives a running time of
$$O\bigl(w^3+m(2m(w-2)+1)\cdot 64\log 64+m(2m(w-2)+1)(2w-3)\cdot 64\bigr).$$
The memory usage is linear in the number of stored states:
$$O\bigl((2m(w-2)+1+2w-3)\cdot 64\bigr).$$
Because the xor dimension is fixed at 64 for the actual problem, the practical growth is dominated by the signed-sum axis rather than by any exponential explosion in the number of Young positions.
Gesucht ist \(R(8,64)\) modulo \(10^9+7\). Die Implementierungen durchlaufen nicht jede Young-Stellung Feld fur Feld. Stattdessen nutzen sie die Zerlegung, die dem Spiel zugrunde liegt: Eine Stellung zerfallt in \(m\) unabhangige diagonale Komponenten, und eine einzelne Komponente wird durch positive ganze Zahlen \(a\) und \(b\) sowie einen Nimber \(g\) beschrieben, mit
$$a\ge 1,\qquad b\ge 1,\qquad 0\le g\le w-a-b-1.$$
Der zugehorige Spielwert hat die Form
$$d+\ast g,\qquad d=b-a.$$
Bei einer Stellung mit \(m\) Komponenten werden die ganzzahligen Teile gewohnlich addiert, wahrend die Nimber per xor kombiniert werden. Deshalb wird die gesamte Stellung durch zwei globale Invarianten beschrieben:
$$D=\sum_{i=1}^m d_i,\qquad X=g_1\oplus g_2\oplus \cdots \oplus g_m.$$
Die Implementierungen zahlen genau die Zustande, die das Endkriterium \(D>0\) oder \(D=0\) mit \(X\ne 0\) erfullen. Nach dieser Reduktion ist das Problem kein direktes Durchmustern von Young-Diagrammen mehr, sondern ein Zahlausdruck uber \((D,X)\).
Die Herleitung besteht aus zwei Ebenen. Zuerst katalogisieren wir alle moglichen Beitrage einer einzelnen diagonalen Komponente. Danach kombinieren wir \(m\) solcher Komponenten mit einer dynamischen Programmierung, die in der Vorzeichenkoordinate gewohnliche Addition und in der Nimber-Koordinate xor verwendet.
Fixiere \(w\). Der Losungscode enumeriert explizit alle Tripel \((a,b,g)\), die die obigen Zulassigkeitsbedingungen erfullen. Schreibt man \(g+1=h\), dann gilt \(h\ge 1\) und
$$a+b+h\le w.$$
Die Gesamtzahl der lokalen Tripel ist also
$$\sum_{a=1}^{w-2}\sum_{b=1}^{w-a-1}(w-a-b)=\binom{w}{3}.$$
Fur die Zielbreite \(w=64\) umfasst dieser lokale Katalog \(\binom{64}{3}=41664\) Eintrage. Fur die globale Rechnung muss jedoch nicht das ganze Tripel gespeichert werden. Entscheidend bleiben nur die Vorzeichendifferenz \(d=b-a\) und der Nimber \(g\).
Verschiedene Paare \((a,b)\) konnen denselben lokalen Wert \(d+\ast g\) erzeugen. Deshalb bauen die Implementierungen die Tabelle
$$C_w(d,g)=\#\left\{(a,b)\in\mathbb Z_{>0}^2:\ b-a=d,\ a+b+g\le w-1\right\}$$
auf. Jeder zulassige Beitrag erhoht genau einen Eintrag dieser Tabelle um 1. Setzt man \(u=w-g-1\), dann lauten die Bedingungen \(b-a=d\) und \(a+b\le u\). Daraus folgt die geschlossene Formel
$$C_w(d,g)=\max\left(0,\left\lfloor\frac{w-g-1-|d|}{2}\right\rfloor\right).$$
Damit werden mehrere Eigenschaften sofort sichtbar: Die Verteilung ist symmetrisch in \(d\), ihr Trager ist endlich, und der grobte mogliche Nimber ist \(w-3\). Fur den Zielwert \(w=64\) bedeutet das \(g\in\{0,1,\dots,61\}\), also genugt eine xor-Dimension der Lange 64.
Sei \(P_t(D,X)\) die Anzahl der Moglichkeiten, \(t\) Komponenten so zu wahlen, dass der gesamte ganzzahlige Anteil \(D\) und der gesamte Nimber \(X\) ist. Die leere Wahl liefert den Anfangszustand
$$P_0(0,0)=1,$$
wahrend alle anderen Zustande fur \(t=0\) verschwinden. Fugt man eine weitere Komponente mit lokalem Wert \(\delta+\ast g\) hinzu, dann addiert sich \(\delta\) im Zahlenteil und \(g\) wirkt per xor auf den Nimber. Daraus ergibt sich exakt die Rekurrenz
$$P_{t+1}(D,X)=\sum_{\delta}\sum_g P_t(D-\delta,\ X\oplus g)\,C_w(\delta,g).$$
Diese Formel ist der Kern der Losung. Sie ersetzt den riesigen Raum moglicher Bretter durch einen kompakten Zustandsraum, der nur noch von einer Vorzeichensumme und einem xor-Wert abhangt.
Nach \(m\) Runden werden nicht einfach alle Zustande aufsummiert. Die Endauswahl der Implementierungen ist in dieser Darstellung sehr direkt: Alle Zustande mit positivem ganzzahligen Teil werden ubernommen, und aus der Zeile \(D=0\) bleiben nur die xor-Zustande ungleich 0. Also
$$R(m,w)=\sum_{D>0}\sum_X P_m(D,X)+\sum_{X\ne 0} P_m(0,X).$$
Der einzige Zustand \((D,X)=(0,0)\) ist der exakte Nullwert des Spiels und muss ausgeschlossen werden. Im Code geschieht das dadurch, dass alle Zeilen mit \(D>0\) vollstandig addiert werden und in der einzigen Zeile \(D=0\) der Eintrag bei xor-Zustand 0 abgezogen wird.
Der teure Teil der Rekurrenz ist die xor-Faltung uber \(X\). Direkt gerechnet musste man jeden alten xor-Zustand mit jedem neuen kombinieren. Stattdessen wenden die Implementierungen auf jede Zeile in der xor-Dimension die XOR-Walsh-Hadamard-Transformation an. Danach wird die xor-Faltung zu einer punktweisen Multiplikation im Frequenzraum:
$$\widehat{P}_{t+1}(D,\omega)=\sum_{\delta}\widehat{P}_t(D-\delta,\omega)\,\widehat{C}_w(\delta,\omega).$$
Damit kann jede Frequenz \(\omega\) unabhangig behandelt werden, und ubrig bleibt nur eine gewohnliche Faltung entlang der Vorzeichensumme. Genau deshalb transformiert der Code zuerst die lokale Tabelle, dann in jeder Runde die aktuelle DP-Tabelle, berechnet pro Frequenz eine normale Faltung und wendet anschliebend die inverse Transformation an.
Fur \(w=4\) sind die zulassigen Tripel
$$ (a,b,g)\in\{(1,1,0),(1,1,1),(1,2,0),(2,1,0)\}. $$
Die einzigen lokalen Werte sind also
$$0,\qquad \ast 1,\qquad 1,\qquad -1.$$
Gleichbedeutend dazu sind die einzigen von null verschiedenen lokalen Anzahlen
$$C_4(0,0)=1,\qquad C_4(0,1)=1,\qquad C_4(1,0)=1,\qquad C_4(-1,0)=1.$$
Bei \(m=2\) bilden wir geordnete Paare dieser vier lokalen Werte und behalten nur Summen mit \(D>0\) oder mit \(D=0\) und nichtverschwindendem Nimber. Gezahlt werden die Paare
$$ (1,1),\ (1,0),\ (0,1),\ (1,\ast 1),\ (\ast 1,1),\ (0,\ast 1),\ (\ast 1,0). $$
Davon gibt es genau 7. Damit stimmt das kleine Kontrollbeispiel mit der Rekurrenz uberein. Der gesamte Algorithmus ist nur die grobe Version derselben Idee.
Die Implementierungen in C++, Python und Java enumerieren zuerst alle zulassigen Tripel \((a,b,g)\) und akkumulieren ihre Vielfachheiten in der Tabelle \(C_w(d,g)\). Fur einfache Array-Indizierung reservieren sie einen etwas groberen Bereich fur die Vorzeichendifferenz, als mathematisch tatsachlich benotigt wird. Dasselbe Prinzip wird spater fur die globale Summenachse verwendet, damit jeder mogliche Gesamtwert \(D\) mit einem festen Offset gespeichert werden kann.
Die aktuelle Zustandsverteilung startet bei der leeren Stellung \((D,X)=(0,0)\). In jeder der \(m\) Runden wird jede xor-Zeile transformiert, die transformierte lokale Tabelle gegen die transformierte Zustandsverteilung fur jede der 64 Frequenzen gefaltet und danach durch eine inverse Walsh-Hadamard-Transformation wieder in den xor-Raum zuruckgeholt. Die Rekurrenz ist in allen drei Sprachen identisch. Die C++-Implementierung parallelisiert zusatzlich die unabhangigen Frequenzschleifen, ohne die Mathematik zu andern.
Nach der letzten Runde entspricht jede Zeile einem moglichen Gesamtwert \(D\). Die Summe uber diese Zeile ist \(\sum_X P_m(D,X)\). Zeilen mit positivem \(D\) werden vollstandig addiert. Fur die einzige Zeile mit \(D=0\) wird der Eintrag bei xor-Wert 0 entfernt. Genau so wird die obige Formel fur \(R(m,w)\) umgesetzt.
Der Aufbau des lokalen Katalogs kostet \(O(w^3)\) Zeit, weil die zulassigen Tripel \((a,b,g)\) explizit erzeugt werden. Die transformierte dynamische Programmierung arbeitet mit einer lokalen Differenztabelle von \(2w-3\) reservierten Zeilen und einer globalen Summenachse von \(2m(w-2)+1\) reservierten Zeilen, jeweils mit 64 xor-Eintragen.
In jeder der \(m\) Runden werden Walsh-Hadamard-Transformationen auf allen globalen Zeilen ausgefuhrt und anschliebend 64 gewohnliche Faltungen gegen die lokale Tabelle berechnet. Dadurch ergibt sich die Laufzeit
$$O\bigl(w^3+m(2m(w-2)+1)\cdot 64\log 64+m(2m(w-2)+1)(2w-3)\cdot 64\bigr).$$
Der Speicherbedarf ist linear in der Anzahl der gespeicherten Zustande:
$$O\bigl((2m(w-2)+1+2w-3)\cdot 64\bigr).$$
Da die xor-Dimension in der eigentlichen Aufgabe fest auf 64 beschrankt ist, wird das praktische Wachstum vor allem von der Vorzeichensummen-Achse bestimmt und nicht von einer exponentiellen Explosion der Young-Stellungen.
Aranan buyukluk \(R(8,64)\)'tur ve sonuc \(10^9+7\) modunda istenir. Uygulamalar Young konumlarini hucre hucre dogrudan gezmez. Bunun yerine oyunun kullandigi ayrisimi esas alir: bir konum \(m\) tane bagimsiz kosegen bilesene ayrilir ve tek bir bilesen, pozitif \(a\) ve \(b\) tam sayilari ile bir nimber \(g\) tarafindan
$$a\ge 1,\qquad b\ge 1,\qquad 0\le g\le w-a-b-1$$
kosuluyla tanimlanir. Bu bilesenin oyun degeri
$$d+\ast g,\qquad d=b-a$$
seklindedir. \(m\) bilesenli bir konumda sayisal kisimlar normal toplama ile, nimber kisimlari ise xor ile birlesir. Dolayisiyla tum konum yalnizca su iki global invarianta indirgenir:
$$D=\sum_{i=1}^m d_i,\qquad X=g_1\oplus g_2\oplus \cdots \oplus g_m.$$
Uygulamalar tam olarak \(D>0\) ya da \(D=0\) iken \(X\ne 0\) kosulunu saglayan durumlari sayar. Bu gozlemden sonra problem, Young diyagramlari uzerinde dolasmaktan cikarak \((D,X)\) ciftleri uzerinde bir sayim problemine donusur.
Turetim iki katmandan olusur. Ilk olarak tek bir kosegen bilesenin butun olasi katkilarini kataloglariz. Daha sonra \(m\) tane bileseni, isaretli fark ekseninde normal toplama ve nimber ekseninde xor kullanan bir dinamik program ile birlestiririz.
\(w\) sabit olsun. Cozum kodu yukaridaki uygunluk kosullarini saglayan tum \((a,b,g)\) uclulerini acikca gezer. \(g+1=h\) yazarsak \(h\ge 1\) olur ve
$$a+b+h\le w$$
esitsizligini elde ederiz. Boylece yerel uclu sayisi
$$\sum_{a=1}^{w-2}\sum_{b=1}^{w-a-1}(w-a-b)=\binom{w}{3}$$
olur. Hedef genislik \(w=64\) icin bu yerel katalog \(\binom{64}{3}=41664\) oge icerir. Fakat global hesapta butun ucluyu hatirlamaya gerek yoktur. Sonraki asamalara sadece isaretli fark \(d=b-a\) ile nimber \(g\) tasinir.
Farkli \((a,b)\) ciftleri ayni yerel degeri \(d+\ast g\) uretebilir. Bu yuzden uygulamalar
$$C_w(d,g)=\#\left\{(a,b)\in\mathbb Z_{>0}^2:\ b-a=d,\ a+b+g\le w-1\right\}$$
tablosunu kurar. Her uygun uclu bu tablonun tam olarak bir hucresini 1 artirir. \(u=w-g-1\) dersek kosullar \(b-a=d\) ve \(a+b\le u\) haline gelir. Buradan su kapali form cikiyor:
$$C_w(d,g)=\max\left(0,\left\lfloor\frac{w-g-1-|d|}{2}\right\rfloor\right).$$
Bu formul birkac seyi acikca gosterir: dagilim \(d\) acisindan simetriktir, destek sonludur ve mumkun en buyuk nimber \(w-3\)'tur. Hedef durumda \(w=64\) oldugu icin \(g\in\{0,1,\dots,61\}\) olur; dolayisiyla uzunlugu 64 olan bir xor ekseni yeterlidir.
\(P_t(D,X)\), toplam \(t\) bilesen secildiginde birlesik sayisal kismin \(D\), birlesik nimberin ise \(X\) oldugu secim sayisi olsun. Bos secim icin baslangic durumu
$$P_0(0,0)=1$$
olur; \(t=0\) icin diger butun durumlar sifirdir. Yeni eklenen bir bilesenin yerel degeri \(\delta+\ast g\) ise, sayisal kisim \(\delta\) kadar kayar, nimber ise \(g\) ile xor yapar. Boylece tam yineleme
$$P_{t+1}(D,X)=\sum_{\delta}\sum_g P_t(D-\delta,\ X\oplus g)\,C_w(\delta,g)$$
seklini alir. Bu ifade cozumun merkezidir. Cok buyuk tahta uzayini, yalnizca bir isaretli toplam ve bir xor degeriyle etiketlenen sikisik bir durum uzayina indirger.
\(m\) turun sonunda butun durumlar toplanmaz. Bu temsilde uygulamalarin son secim kurali dogrudan okunur: sayisal kismi pozitif olan tum durumlar alinir, \(D=0\) satirinda ise yalnizca xor degeri sifir olmayan durumlar tutulur. Dolayisiyla
$$R(m,w)=\sum_{D>0}\sum_X P_m(D,X)+\sum_{X\ne 0} P_m(0,X)$$
olur. \((D,X)=(0,0)\) durumu oyunun tam sifir degeridir ve disarida birakilmalidir. Kodda bu, \(D>0\) olan tum satirlari tam olarak toplayip \(D=0\) olan tek satirda xor durumu 0 hucresini cikarmakla uygulanir.
Yinelemenin pahali tarafi \(X\) uzerindeki xor-konvolusyonudur. Dogrudan yapilirsa her eski xor durumu her yeni xor durumu ile karsilastirilmak zorunda kalir. Bunun yerine uygulamalar xor boyutundaki her satira XOR Walsh-Hadamard donusumu uygular. Bu donusumden sonra xor-konvolusyonu frekans uzayinda noktasal carpima donusur:
$$\widehat{P}_{t+1}(D,\omega)=\sum_{\delta}\widehat{P}_t(D-\delta,\omega)\,\widehat{C}_w(\delta,\omega).$$
Boylece her frekans \(\omega\) bagimsiz islenebilir ve geriye yalnizca isaretli-toplam ekseninde normal bir konvolusyon kalir. Kodun once yerel tabloyu, sonra her turda guncel DP tablosunu donusturmesi, frekans bazinda konvolusyonu yapmasi ve sonunda ters donusum uygulamasi tam olarak bu nedendendir.
\(w=4\) icin uygun ucluler
$$ (a,b,g)\in\{(1,1,0),(1,1,1),(1,2,0),(2,1,0)\} $$
olur. Dolayisiyla tek mumkun yerel degerler
$$0,\qquad \ast 1,\qquad 1,\qquad -1$$
seklindedir. Baska bir deyisle sifirdan farkli tek yerel sayilar
$$C_4(0,0)=1,\qquad C_4(0,1)=1,\qquad C_4(1,0)=1,\qquad C_4(-1,0)=1$$
olur. \(m=2\) icin bu dort yerel degerin sirali ikililerini kurar, yalnizca \(D>0\) olanlari veya \(D=0\) iken nimberi sifir olmayanlari tutariz. Sayilan ikililer
$$ (1,1),\ (1,0),\ (0,1),\ (1,\ast 1),\ (\ast 1,1),\ (0,\ast 1),\ (\ast 1,0) $$
olur. Toplam 7 tane vardir. Kucuk dogrulama ornegi ile yineleme tam olarak ortusur. Tum algoritma bunun daha buyuk olcekteki halidir.
C++, Python ve Java uygulamalari once tum uygun \((a,b,g)\) uclulerini gezer ve bunlarin cokluklerini \(C_w(d,g)\) tablosunda toplar. Dizi indekslerini kolaylastirmak icin, matematiksel olarak gerekli olandan biraz daha genis bir isaretli-fark araligi ayirirlar. Ayni fikir daha sonra global toplam ekseninde de kullanilir; boylece her mumkun \(D\) degeri sabit bir ofset ile saklanabilir.
Mevcut durum dagilimi bos durum \((D,X)=(0,0)\) ile baslar. \(m\) turun her birinde xor satirlari donusturulur, donusmus yerel tablo ile donusmus durum tablosu 64 frekansin her biri icin bagimsiz olarak konvolusyonlanir ve ardindan ters Walsh-Hadamard donusumu ile sonuc tekrar xor uzayina getirilir. Uc dilde de yineleme aynidir. C++ uygulamasi ek olarak birbirinden bagimsiz frekans dongulerini paralellestirir, fakat matematik degismez.
Son turun ardindan her satir bir olasi toplam \(D\) degerine karsilik gelir. O satirdaki toplam \(\sum_X P_m(D,X)\) olur. Pozitif \(D\) veren satirlar dogrudan eklenir. \(D=0\) olan tek satirda ise xor degeri 0 olan hucre cikarilir. Boylece yukaridaki \(R(m,w)\) formulu birebir uygulanmis olur.
Yerel katalogu kurmak \(O(w^3)\) zaman alir; cunku uygun \((a,b,g)\) ucluleri acikca uretilir. Donusmus dinamik program, \(2w-3\) adet ayirilmis yerel fark satiri ve \(2m(w-2)+1\) adet ayirilmis global toplam satiri kullanir; her satirda 64 xor hucresi bulunur.
\(m\) turun her birinde tum global satirlarda Walsh-Hadamard donusumu yapilir ve ardindan yerel tabloya karsi 64 normal konvolusyon hesaplanir. Buna gore calisma suresi
$$O\bigl(w^3+m(2m(w-2)+1)\cdot 64\log 64+m(2m(w-2)+1)(2w-3)\cdot 64\bigr)$$
seklindedir. Bellek kullanimi ise durum sayisiyla dogrusal olur:
$$O\bigl((2m(w-2)+1+2w-3)\cdot 64\bigr).$$
Gercek soruda xor boyutu 64'te sabit oldugu icin, pratikte buyume Young konumlarinin sayisindaki ussel patlamadan degil, esas olarak isaretli-toplam ekseninin genislemesinden gelir.
La cantidad buscada es \(R(8,64)\) modulo \(10^9+7\). Las implementaciones no recorren todas las posiciones de Young casilla por casilla. En lugar de eso, usan la descomposicion propia del juego: una posicion se separa en \(m\) componentes diagonales independientes, y cada componente queda determinado por enteros positivos \(a\) y \(b\) junto con un nimber \(g\), con
$$a\ge 1,\qquad b\ge 1,\qquad 0\le g\le w-a-b-1.$$
El valor del componente tiene la forma
$$d+\ast g,\qquad d=b-a.$$
En una posicion con \(m\) componentes, las partes enteras se suman de manera ordinaria y las partes nimber se combinan por xor. Por eso toda la posicion queda resumida por dos invariantes globales:
$$D=\sum_{i=1}^m d_i,\qquad X=g_1\oplus g_2\oplus \cdots \oplus g_m.$$
Las implementaciones cuentan exactamente los estados que satisfacen el criterio final \(D>0\), o bien \(D=0\) con \(X\ne 0\). Una vez hecha esa reduccion, el problema deja de ser una exploracion directa de diagramas de Young y pasa a ser un conteo sobre pares \((D,X)\).
La derivacion tiene dos capas. Primero catalogamos todas las contribuciones posibles de un solo componente diagonal. Despues combinamos \(m\) de esos componentes con una programacion dinamica que usa suma ordinaria en la coordenada de diferencia con signo y xor en la coordenada nimber.
Fijemos \(w\). El codigo de la solucion enumera de forma explicita todos los ternas \((a,b,g)\) que satisfacen las condiciones de admisibilidad anteriores. Si escribimos \(g+1=h\), entonces \(h\ge 1\) y
$$a+b+h\le w.$$
Asi, el numero total de ternas locales es
$$\sum_{a=1}^{w-2}\sum_{b=1}^{w-a-1}(w-a-b)=\binom{w}{3}.$$
Para la anchura objetivo \(w=64\), ese catalogo local tiene \(\binom{64}{3}=41664\) entradas. Sin embargo, el calculo global no necesita conservar toda la terna. Solo sobreviven la diferencia con signo \(d=b-a\) y el nimber \(g\).
Distintos pares \((a,b)\) pueden producir el mismo valor local \(d+\ast g\). Por eso las implementaciones construyen la tabla
$$C_w(d,g)=\#\left\{(a,b)\in\mathbb Z_{>0}^2:\ b-a=d,\ a+b+g\le w-1\right\}.$$
Cada terna admisible incrementa exactamente una celda de esa tabla. Si definimos \(u=w-g-1\), entonces las restricciones pasan a ser \(b-a=d\) y \(a+b\le u\). Resolver esas ecuaciones da la formula cerrada
$$C_w(d,g)=\max\left(0,\left\lfloor\frac{w-g-1-|d|}{2}\right\rfloor\right).$$
Esto aclara varias propiedades a la vez: la distribucion es simetrica en \(d\), su soporte es finito y el nimber maximo posible es \(w-3\). En el caso objetivo \(w=64\), eso significa \(g\in\{0,1,\dots,61\}\), de modo que una dimension xor de tamano 64 basta para todos los estados.
Sea \(P_t(D,X)\) el numero de formas de elegir \(t\) componentes cuya parte entera total sea \(D\) y cuyo nimber total sea \(X\). La eleccion vacia produce el estado inicial
$$P_0(0,0)=1,$$
y todos los demas estados valen cero cuando \(t=0\). Si se anade un nuevo componente con valor local \(\delta+\ast g\), la parte entera se desplaza en \(\delta\) y la parte nimber se combina con xor por \(g\). Asi se obtiene la recurrencia exacta
$$P_{t+1}(D,X)=\sum_{\delta}\sum_g P_t(D-\delta,\ X\oplus g)\,C_w(\delta,g).$$
Esta es la formula central de la solucion. Sustituye un espacio enorme de tableros por un espacio de estados compacto indexado solo por una suma con signo y un valor xor.
Despues de \(m\) rondas no se suman todos los estados. En esta representacion, la seleccion final usada por las implementaciones es directa: se conservan todas las filas con parte entera positiva y, en la fila \(D=0\), solo los estados xor no nulos. Por tanto,
$$R(m,w)=\sum_{D>0}\sum_X P_m(D,X)+\sum_{X\ne 0} P_m(0,X).$$
El unico estado \((D,X)=(0,0)\) representa el valor exactamente nulo del juego y debe excluirse. En el codigo esto se implementa sumando completas todas las filas con \(D>0\) y, en la unica fila con \(D=0\), restando la entrada del estado xor 0.
La parte costosa de la recurrencia es la xor-convolucion en \(X\). Una implementacion directa tendria que comparar todos los estados xor anteriores con todos los nuevos estados xor. En su lugar, las implementaciones aplican la transformada XOR Walsh-Hadamard a cada fila en la dimension xor. Despues de esa transformacion, la xor-convolucion se convierte en multiplicacion puntual en el espacio de frecuencias:
$$\widehat{P}_{t+1}(D,\omega)=\sum_{\delta}\widehat{P}_t(D-\delta,\omega)\,\widehat{C}_w(\delta,\omega).$$
Ahora cada frecuencia \(\omega\) puede procesarse de forma independiente y solo queda una convolucion ordinaria a lo largo del eje de sumas con signo. Precisamente por eso el codigo transforma primero la tabla local, luego transforma la tabla dinamica en cada ronda, hace una convolucion normal por frecuencia y por ultimo aplica la transformada inversa.
Cuando \(w=4\), las ternas admisibles son
$$ (a,b,g)\in\{(1,1,0),(1,1,1),(1,2,0),(2,1,0)\}. $$
Por tanto, los unicos valores locales posibles son
$$0,\qquad \ast 1,\qquad 1,\qquad -1.$$
De forma equivalente, las unicas cuentas locales no nulas son
$$C_4(0,0)=1,\qquad C_4(0,1)=1,\qquad C_4(1,0)=1,\qquad C_4(-1,0)=1.$$
Para \(m=2\), formamos pares ordenados de esos cuatro valores locales y conservamos solo los totales con \(D>0\), o con \(D=0\) y nimber no nulo. Los pares contados son
$$ (1,1),\ (1,0),\ (0,1),\ (1,\ast 1),\ (\ast 1,1),\ (0,\ast 1),\ (\ast 1,0). $$
Hay exactamente 7 pares de este tipo, en perfecto acuerdo con la pequena comprobacion utilizada por las implementaciones. El metodo completo no es mas que esta misma idea a gran escala.
Las implementaciones en C++, Python y Java recorren primero todas las ternas admisibles \((a,b,g)\) y acumulan sus multiplicidades en la tabla \(C_w(d,g)\). Para simplificar los indices de los arreglos, reservan un rango de diferencias con signo algo mas amplio de lo estrictamente necesario desde el punto de vista matematico. La misma idea se usa despues para el eje global de sumas, de modo que cualquier valor posible de \(D\) pueda guardarse con un desplazamiento fijo.
La distribucion de estados empieza en el estado vacio \((D,X)=(0,0)\). En cada una de las \(m\) rondas, todas las filas xor se transforman, la tabla local transformada se combina con la distribucion transformada de manera independiente para cada una de las 64 frecuencias y, al final, una transformada inversa de Walsh-Hadamard devuelve el resultado al espacio xor original. La recurrencia es identica en los tres lenguajes. La implementacion en C++ ademas paraleliza los bucles de frecuencia, que son independientes, pero la matematica no cambia.
Tras la ultima ronda, cada fila corresponde a un valor total posible \(D\). La suma a lo largo de esa fila es \(\sum_X P_m(D,X)\). Las filas con \(D\) positivo se agregan completas. Para la unica fila con \(D=0\), se elimina la entrada con valor xor 0. Asi se implementa exactamente la formula anterior para \(R(m,w)\).
Construir el catalogo local cuesta \(O(w^3)\) tiempo, porque las ternas admisibles \((a,b,g)\) se generan de forma explicita. La programacion dinamica transformada usa una tabla local de diferencias con \(2w-3\) filas reservadas y una tabla global de sumas con \(2m(w-2)+1\) filas reservadas, cada una con 64 entradas xor.
En cada una de las \(m\) rondas, el algoritmo aplica transformadas Walsh-Hadamard a todas las filas globales y luego ejecuta 64 convoluciones ordinarias contra la tabla local. Por tanto, el tiempo total es
$$O\bigl(w^3+m(2m(w-2)+1)\cdot 64\log 64+m(2m(w-2)+1)(2w-3)\cdot 64\bigr).$$
El uso de memoria es lineal en el numero de estados almacenados:
$$O\bigl((2m(w-2)+1+2w-3)\cdot 64\bigr).$$
Como la dimension xor queda fijada en 64 para el problema real, el crecimiento practico viene dominado por el eje de sumas con signo y no por una explosion exponencial del numero de posiciones de Young.
要求的是 \(R(8,64)\) 在模 \(10^9+7\) 下的值。实现并不是把所有 Young 局面逐格展开，而是利用这个游戏在题目中对应的分解方式：一个局面可以拆成 \(m\) 个彼此独立的对角分量，而单个分量由正整数 \(a\)、\(b\) 和一个 nimber \(g\) 描述，并满足
$$a\ge 1,\qquad b\ge 1,\qquad 0\le g\le w-a-b-1.$$
该分量的游戏值写成
$$d+\ast g,\qquad d=b-a.$$
在 \(m\) 个分量组成的局面中，整数部分按通常加法合并，nimber 部分按 xor 合并。所以整个局面最终只由两个全局不变量控制：
$$D=\sum_{i=1}^m d_i,\qquad X=g_1\oplus g_2\oplus \cdots \oplus g_m.$$
实现真正统计的，正是满足最终判定 \(D>0\)，或者 \(D=0\) 且 \(X\ne 0\) 的状态。一旦识别出这种压缩方式，问题就从“枚举 Young 图形”转化为“统计有多少种选择会落在每个 \((D,X)\) 状态上”。
整个推导可以分成两层。第一层先把单个对角分量的一切可能贡献整理成一个局部目录。第二层再用动态规划把 \(m\) 个分量拼起来，其中带符号差值方向使用普通加法，nimber 方向使用 xor。
固定 \(w\)。解法代码会显式枚举所有满足上面条件的三元组 \((a,b,g)\)。如果把 \(g+1\) 改写为一个新的正整数 \(h\)，那么条件就变成
$$a+b+h\le w.$$
因此局部三元组总数恰好是
$$\sum_{a=1}^{w-2}\sum_{b=1}^{w-a-1}(w-a-b)=\binom{w}{3}.$$
在目标参数 \(w=64\) 下，这个局部目录共有 \(\binom{64}{3}=41664\) 个条目。不过全局计算并不需要记住完整三元组。真正会被带到后续步骤中的，只有带符号差值 \(d=b-a\) 与 nimber \(g\)。
不同的 \((a,b)\) 可能产生同一个局部值 \(d+\ast g\)。因此实现先建立一张重数表
$$C_w(d,g)=\#\left\{(a,b)\in\mathbb Z_{>0}^2:\ b-a=d,\ a+b+g\le w-1\right\}.$$
每一个合法三元组都会把这张表中的某一个单元加 1。若设 \(u=w-g-1\)，那么约束就变成 \(b-a=d\) 与 \(a+b\le u\)。把这两个条件联立，可以得到闭式
$$C_w(d,g)=\max\left(0,\left\lfloor\frac{w-g-1-|d|}{2}\right\rfloor\right).$$
这个公式直接解释了代码里的若干事实：表对 \(d\) 是对称的，支持范围是有限的，而且最大的可能 nimber 是 \(w-3\)。在目标情形 \(w=64\) 中，这意味着 \(g\in\{0,1,\dots,61\}\)，所以长度为 64 的 xor 维度就已经足够。
记 \(P_t(D,X)\) 为选取 \(t\) 个分量后，总整数部分等于 \(D\)、总 nimber 等于 \(X\) 的方案数。空选择给出初始状态
$$P_0(0,0)=1,$$
而在 \(t=0\) 时其余状态都为零。若新加入一个局部值为 \(\delta+\ast g\) 的分量，那么整数部分增加 \(\delta\)，nimber 部分与 \(g\) 做 xor，于是得到精确递推式
$$P_{t+1}(D,X)=\sum_{\delta}\sum_g P_t(D-\delta,\ X\oplus g)\,C_w(\delta,g).$$
这就是整套解法的核心公式。它把巨大的棋盘状态空间压缩成一个只由带符号总和和 xor 值标记的紧凑状态空间。
做完 \(m\) 轮以后，并不是把所有状态都累加起来。在这种表示里，实现采用的最终筛选规则非常直接：保留所有整数部分为正的状态；在 \(D=0\) 那一行里，只保留 xor 值非零的状态。因此
$$R(m,w)=\sum_{D>0}\sum_X P_m(D,X)+\sum_{X\ne 0} P_m(0,X).$$
唯一的状态 \((D,X)=(0,0)\) 代表游戏值恰好为零，必须排除。代码里的实现方式正是：把所有 \(D>0\) 的整行全部加入答案，而在唯一的 \(D=0\) 那一行中减去 xor 状态 0 的那一格。
递推里最慢的部分，是 \(X\) 这一维上的 xor 卷积。若直接做，每一步都要把所有旧 xor 状态与所有新 xor 状态成对比较。实现采用的办法是：对 xor 维度上的每一行施加 XOR Walsh-Hadamard 变换。变换以后，xor 卷积会在频域里变成点乘：
$$\widehat{P}_{t+1}(D,\omega)=\sum_{\delta}\widehat{P}_t(D-\delta,\omega)\,\widehat{C}_w(\delta,\omega).$$
于是每一个频率 \(\omega\) 都可以独立处理，剩下的只是在带符号总和轴上的普通卷积。这也解释了代码的整体流程：先把局部表做变换，再在每一轮把当前 DP 表变换到频域，对每个频率分别做一次普通卷积，最后再做逆变换回到 xor 空间。
当 \(w=4\) 时，允许的三元组只有
$$ (a,b,g)\in\{(1,1,0),(1,1,1),(1,2,0),(2,1,0)\}. $$
因此仅有四种局部值：
$$0,\qquad \ast 1,\qquad 1,\qquad -1.$$
等价地说，唯一非零的局部计数为
$$C_4(0,0)=1,\qquad C_4(0,1)=1,\qquad C_4(1,0)=1,\qquad C_4(-1,0)=1.$$
在 \(m=2\) 时，我们取这四个局部值的有序二元组，只保留总值满足 \(D>0\) 或者 \(D=0\) 且 nimber 非零的情况。被计入的二元组正好是
$$ (1,1),\ (1,0),\ (0,1),\ (1,\ast 1),\ (\ast 1,1),\ (0,\ast 1),\ (\ast 1,0). $$
一共恰好 7 个，与实现中使用的小型校验值完全一致。这个小例子已经浓缩了完整算法的全部结构：先建局部目录，再通过 \((D,X)\) 组合，最后套用“哪些值算正”的判定规则。
C++、Python 和 Java 实现都会先遍历所有合法的 \((a,b,g)\) 三元组，并把它们的重数累加到表 \(C_w(d,g)\) 里。为了让数组下标处理更简单，实现会给带符号差值预留一个比真实数学支持范围稍宽的区间。之后全局带符号总和轴也采用同样的做法，这样每个可能的 \(D\) 都能通过一个固定偏移映射到数组位置。
当前状态分布从空状态 \((D,X)=(0,0)\) 开始。在每一轮中，所有 xor 行都会先被变换，接着把变换后的局部表与变换后的状态表在 64 个频率上分别做独立卷积，最后用逆 Walsh-Hadamard 变换把结果送回原始 xor 空间。三种语言实现的递推完全一致。只有 C++ 版本额外把彼此独立的频率循环并行化，但数学内容没有变化。
最后一轮结束后，每一行对应一个可能的总和 \(D\)。该行所有单元求和就是 \(\sum_X P_m(D,X)\)。所有 \(D>0\) 的行都整行加入答案。对于唯一的 \(D=0\) 那一行，则去掉 xor 值为 0 的单元。这样就精确实现了上面的 \(R(m,w)\) 公式。
构造局部目录需要 \(O(w^3)\) 时间，因为合法的 \((a,b,g)\) 三元组是显式枚举出来的。变换后的动态规划使用一张有 \(2w-3\) 个预留差值行的局部表，以及一张有 \(2m(w-2)+1\) 个预留总和行的全局表；每一行都有 64 个 xor 状态。
在 \(m\) 轮中的每一轮，算法都会对所有全局行做 Walsh-Hadamard 变换，然后针对局部表执行 64 次普通卷积。因此总时间复杂度为
$$O\bigl(w^3+m(2m(w-2)+1)\cdot 64\log 64+m(2m(w-2)+1)(2w-3)\cdot 64\bigr).$$
空间复杂度与存储状态数量线性相关：
$$O\bigl((2m(w-2)+1+2w-3)\cdot 64\bigr).$$
由于真实题目的 xor 维度固定为 64，实际增长主要由带符号总和轴决定，而不是来自 Young 局面数量的指数爆炸。
Требуется найти \(R(8,64)\) по модулю \(10^9+7\). Реализации не перебирают все позиции Young по клеткам. Вместо этого они используют разложение, лежащее в основе игры: позиция распадается на \(m\) независимых диагональных компонентов, а один компонент задается положительными целыми \(a\) и \(b\) и нимбером \(g\), для которых выполнено
$$a\ge 1,\qquad b\ge 1,\qquad 0\le g\le w-a-b-1.$$
Значение такого компонента имеет вид
$$d+\ast g,\qquad d=b-a.$$
В позиции из \(m\) компонентов целые части складываются обычным образом, а нимберные части объединяются по xor. Поэтому вся позиция полностью задается двумя глобальными инвариантами:
$$D=\sum_{i=1}^m d_i,\qquad X=g_1\oplus g_2\oplus \cdots \oplus g_m.$$
Реализации считают ровно те состояния, которые удовлетворяют финальному критерию \(D>0\), либо \(D=0\) и \(X\ne 0\). После такой редукции задача превращается не в прямой перебор диаграмм Young, а в подсчет числа способов получить каждую пару \((D,X)\).
Вывод состоит из двух уровней. Сначала нужно каталогизировать все возможные вклады одного диагонального компонента. Затем \(m\) таких компонентов объединяются динамикой, в которой по координате знаковой суммы действует обычное сложение, а по координате нимбера действует xor.
Зафиксируем \(w\). Код решения явно перебирает все тройки \((a,b,g)\), удовлетворяющие указанным условиям допустимости. Если ввести новую положительную величину \(h=g+1\), то условия перепишутся как
$$a+b+h\le w.$$
Отсюда общее число локальных троек равно
$$\sum_{a=1}^{w-2}\sum_{b=1}^{w-a-1}(w-a-b)=\binom{w}{3}.$$
Для целевого значения \(w=64\) локальный каталог содержит \(\binom{64}{3}=41664\) записей. Но в глобальном подсчете не нужно помнить всю тройку. В дальнейшие шаги переходят только знаковая разность \(d=b-a\) и нимбер \(g\).
Разные пары \((a,b)\) могут давать один и тот же локальный элемент \(d+\ast g\). Поэтому реализации строят таблицу
$$C_w(d,g)=\#\left\{(a,b)\in\mathbb Z_{>0}^2:\ b-a=d,\ a+b+g\le w-1\right\}.$$
Каждая допустимая тройка увеличивает ровно одну ячейку этой таблицы на 1. Если положить \(u=w-g-1\), то ограничения примут вид \(b-a=d\) и \(a+b\le u\). Решение этих условий дает явную формулу
$$C_w(d,g)=\max\left(0,\left\lfloor\frac{w-g-1-|d|}{2}\right\rfloor\right).$$
Из нее сразу видны несколько свойств: распределение симметрично по \(d\), носитель конечен, а максимальный возможный нимбер равен \(w-3\). В целевом случае \(w=64\) это означает \(g\in\{0,1,\dots,61\}\), так что xor-пространства размера 64 вполне достаточно.
Пусть \(P_t(D,X)\) обозначает число способов выбрать \(t\) компонентов так, чтобы суммарная целая часть была равна \(D\), а суммарный нимбер был равен \(X\). Пустой выбор задает начальное состояние
$$P_0(0,0)=1,$$
а все остальные состояния при \(t=0\) равны нулю. Если добавить компонент с локальным значением \(\delta+\ast g\), то целая часть сдвигается на \(\delta\), а нимбер xорится с \(g\). Поэтому получается точная рекурсия
$$P_{t+1}(D,X)=\sum_{\delta}\sum_g P_t(D-\delta,\ X\oplus g)\,C_w(\delta,g).$$
Это центральная формула решения. Она заменяет огромное пространство досок компактным пространством состояний, индексируемым только знаковой суммой и xor-значением.
После \(m\) раундов нужно суммировать не все состояния. В этой записи финальный отбор реализуется напрямую: берутся все состояния с положительной целой частью, а в строке \(D=0\) сохраняются только ненулевые xor-состояния. Следовательно,
$$R(m,w)=\sum_{D>0}\sum_X P_m(D,X)+\sum_{X\ne 0} P_m(0,X).$$
Единственное состояние \((D,X)=(0,0)\) соответствует точному нулевому значению игры и должно быть исключено. В коде это реализовано так: все строки с \(D>0\) суммируются полностью, а в единственной строке \(D=0\) вычитается ячейка с xor-состоянием 0.
Самая дорогая часть рекурсии - xor-свертка по координате \(X\). При прямом подсчете пришлось бы для каждого нового xor-состояния просматривать все предыдущие. Вместо этого реализации применяют XOR-преобразование Уолша-Адамара к каждой строке xor-измерения. После преобразования xor-свертка превращается в покоординатное умножение в частотном пространстве:
$$\widehat{P}_{t+1}(D,\omega)=\sum_{\delta}\widehat{P}_t(D-\delta,\omega)\,\widehat{C}_w(\delta,\omega).$$
Теперь каждую частоту \(\omega\) можно обрабатывать независимо, а от исходной задачи остается только обычная свертка вдоль оси знаковых сумм. Именно поэтому код сначала преобразует локальную таблицу, затем на каждом шаге преобразует текущую DP-таблицу, выполняет по одной обычной свертке на каждую частоту и потом делает обратное преобразование.
При \(w=4\) допустимы только тройки
$$ (a,b,g)\in\{(1,1,0),(1,1,1),(1,2,0),(2,1,0)\}. $$
Значит, возможны лишь четыре локальных значения:
$$0,\qquad \ast 1,\qquad 1,\qquad -1.$$
Эквивалентно, единственные ненулевые локальные подсчеты таковы:
$$C_4(0,0)=1,\qquad C_4(0,1)=1,\qquad C_4(1,0)=1,\qquad C_4(-1,0)=1.$$
Для \(m=2\) берутся упорядоченные пары этих четырех локальных значений и оставляются только те суммы, где \(D>0\), либо \(D=0\) и нимбер ненулевой. В ответ попадают пары
$$ (1,1),\ (1,0),\ (0,1),\ (1,\ast 1),\ (\ast 1,1),\ (0,\ast 1),\ (\ast 1,0). $$
Их ровно 7, что полностью совпадает с малой проверкой, заложенной в реализациях. В этом миниатюрном случае уже видна структура всего метода: локальный каталог, объединение через \((D,X)\) и финальное правило отбора.
Реализации на C++, Python и Java сначала перебирают все допустимые тройки \((a,b,g)\) и накапливают их кратности в таблице \(C_w(d,g)\). Чтобы индексация массивов была проще, для знаковой разности резервируется диапазон немного шире, чем реальный математический носитель. Та же идея затем используется и для глобальной оси сумм, так что любой возможный итоговый \(D\) хранится через фиксированный сдвиг.
Текущее распределение состояний стартует из пустого состояния \((D,X)=(0,0)\). В каждом из \(m\) раундов все xor-строки преобразуются, затем преобразованная локальная таблица сворачивается с преобразованной таблицей состояний независимо по каждой из 64 частот, а после этого обратное преобразование Уолша-Адамара возвращает результат в исходное xor-пространство. Рекурсия одинакова во всех трех языках. Вариант на C++ дополнительно распараллеливает независимые циклы по частотам, но сама математика от этого не меняется.
После последнего раунда каждая строка соответствует некоторому возможному значению \(D\). Сумма по строке равна \(\sum_X P_m(D,X)\). Строки с положительным \(D\) добавляются целиком. Для единственной строки с \(D=0\) удаляется ячейка с xor-значением 0. Именно так реализуется формула для \(R(m,w)\).
Построение локального каталога требует \(O(w^3)\) времени, потому что допустимые тройки \((a,b,g)\) перечисляются явно. Преобразованная динамика использует локальную таблицу разностей с \(2w-3\) зарезервированными строками и глобальную таблицу сумм с \(2m(w-2)+1\) зарезервированными строками, в каждой строке по 64 xor-состояния.
В каждом из \(m\) раундов алгоритм выполняет преобразования Уолша-Адамара на всех глобальных строках, а затем 64 обычные свертки с локальной таблицей. Поэтому итоговое время равно
$$O\bigl(w^3+m(2m(w-2)+1)\cdot 64\log 64+m(2m(w-2)+1)(2w-3)\cdot 64\bigr).$$
Память линейна по числу сохраняемых состояний:
$$O\bigl((2m(w-2)+1+2w-3)\cdot 64\bigr).$$
Поскольку xor-измерение в реальной задаче фиксировано и равно 64, практический рост определяется главным образом шириной оси знаковых сумм, а не экспоненциальным числом позиций Young.
المقدار المطلوب هو \(R(8,64)\) بترديد \(10^9+7\). لا تقوم التطبيقات بتعداد جميع اوضاع Young خانة بخانة، بل تعتمد على التفكيك الذي تستعمله اللعبة نفسها: فالوضع ينقسم الى \(m\) مكونات قطرية مستقلة، وكل مكون يوصف بعددين صحيحين موجبين \(a\) و \(b\) ومعهما nimber يساوي \(g\)، بحيث
$$a\ge 1,\qquad b\ge 1,\qquad 0\le g\le w-a-b-1.$$
وقيمة هذا المكون تكتب على الصورة
$$d+\ast g,\qquad d=b-a.$$
وفي وضع مكون من \(m\) اجزاء، تتجمع الاجزاء العددية بالجمع العادي، بينما تتجمع اجزاء nimber بعملية xor. ولذلك فان الوضع كله يختزل الى ثابتين كليين:
$$D=\sum_{i=1}^m d_i,\qquad X=g_1\oplus g_2\oplus \cdots \oplus g_m.$$
التطبيقات تعد بالضبط الحالات التي تحقق المعيار النهائي \(D>0\)، او \(D=0\) مع \(X\ne 0\). وبعد هذا الاختزال تتحول المسألة من استعراض مباشر لاشكال Young الى مسألة عد فوق الازواج \((D,X)\).
الاشتقاق يتكون من مستويين. اولا نبني فهرسا لكل المساهمات الممكنة لمكون قطري واحد. ثم نجمع \(m\) مكونات من هذا النوع باستعمال برمجة ديناميكية تستخدم الجمع العادي على محور الفروق الموقعة و xor على محور النيمبر.
لنثبت \(w\). يقوم كود الحل بتعداد جميع الثلاثيات \((a,b,g)\) التي تحقق شروط السماحية السابقة. واذا كتبنا \(g+1=h\)، صار لدينا \(h\ge 1\) و
$$a+b+h\le w.$$
ومن ثم فان عدد الثلاثيات المحلية يساوي
$$\sum_{a=1}^{w-2}\sum_{b=1}^{w-a-1}(w-a-b)=\binom{w}{3}.$$
في الحالة المستهدفة \(w=64\)، يحتوي هذا الفهرس المحلي على \(\binom{64}{3}=41664\) عنصرا. لكن الحساب الكلي لا يحتاج الى حفظ الثلاثية كاملة؛ فما ينتقل الى المراحل التالية هو فقط الفرق الموقع \(d=b-a\) والنيمبر \(g\).
من الممكن لازواج مختلفة \((a,b)\) ان تعطي القيمة المحلية نفسها \(d+\ast g\). لهذا تبني التطبيقات الجدول
$$C_w(d,g)=\#\left\{(a,b)\in\mathbb Z_{>0}^2:\ b-a=d,\ a+b+g\le w-1\right\}.$$
كل ثلاثية صالحة تزيد خلية واحدة فقط من هذا الجدول بمقدار 1. واذا وضعنا \(u=w-g-1\)، صارت القيود هي \(b-a=d\) و \(a+b\le u\). ومن حل هذه القيود نحصل على الصيغة المغلقة
$$C_w(d,g)=\max\left(0,\left\lfloor\frac{w-g-1-|d|}{2}\right\rfloor\right).$$
هذه الصيغة توضح عدة امور دفعة واحدة: التوزيع متناظر في \(d\)، والدعم منته، واكبر nimber ممكن هو \(w-3\). وفي الحالة الهدف \(w=64\) يكون \(g\in\{0,1,\dots,61\}\)، ولذلك يكفي فضاء xor طوله 64.
ليكن \(P_t(D,X)\) هو عدد الطرق لاختيار \(t\) مكونات بحيث يكون الجزء العددي الكلي \(D\) والنيمبر الكلي \(X\). الاختيار الفارغ يعطي الحالة الابتدائية
$$P_0(0,0)=1,$$
وجميع الحالات الاخرى تساوي صفرا عندما \(t=0\). وعند اضافة مكون جديد قيمته المحلية \(\delta+\ast g\)، يزداد الجزء العددي بمقدار \(\delta\) ويتغير النيمبر بعملية xor مع \(g\). ومن هنا نحصل على العلاقة الدقيقة
$$P_{t+1}(D,X)=\sum_{\delta}\sum_g P_t(D-\delta,\ X\oplus g)\,C_w(\delta,g).$$
وهذه هي المعادلة المركزية في الحل. فهي تستبدل فضاء الالواح الضخم بفضاء حالات صغير يفهرس فقط بمجموع موقع وقيمة xor.
بعد \(m\) جولات لا نجمع كل الحالات. وفي هذا التمثيل تصبح قاعدة الاختيار النهائية مباشرة: نحتفظ بكل حالة يكون جزؤها العددي موجبا، ومن الصف \(D=0\) نحتفظ فقط بحالات xor غير الصفرية. ولذلك
$$R(m,w)=\sum_{D>0}\sum_X P_m(D,X)+\sum_{X\ne 0} P_m(0,X).$$
الحالة الوحيدة \((D,X)=(0,0)\) تمثل القيمة الصفرية التامة للعبة، ولذلك يجب حذفها. وفي الكود يتم ذلك بجمع كل الصفوف التي تحقق \(D>0\) كاملة، ثم طرح الخانة ذات xor صفر من الصف الوحيد الذي يحقق \(D=0\).
الجزء المكلف في العلاقة هو xor-convolution على البعد \(X\). ولو حسب مباشرة لاحتجنا الى مقارنة كل حالة xor قديمة بكل حالة جديدة. لذلك تطبق التطبيقات تحويل XOR Walsh-Hadamard على كل صف من صفوف بعد xor. وبعد هذا التحويل تصبح xor-convolution ضربا نقطيا في فضاء التردد:
$$\widehat{P}_{t+1}(D,\omega)=\sum_{\delta}\widehat{P}_t(D-\delta,\omega)\,\widehat{C}_w(\delta,\omega).$$
وبذلك يمكن معالجة كل تردد \(\omega\) بصورة مستقلة، ولا يبقى الا التفاف عادي على محور المجموعات الموقعة. ولهذا السبب يقوم الكود اولا بتحويل الجدول المحلي، ثم يحول جدول البرمجة الديناميكية في كل جولة، ويجري التفافا عاديا لكل تردد، ثم يطبق التحويل العكسي.
عندما \(w=4\)، تكون الثلاثيات المسموح بها هي
$$ (a,b,g)\in\{(1,1,0),(1,1,1),(1,2,0),(2,1,0)\}. $$
ولذلك لا توجد الا القيم المحلية الاربع
$$0,\qquad \ast 1,\qquad 1,\qquad -1.$$
وبصورة مكافئة، فان القيم المحلية غير الصفرية الوحيدة هي
$$C_4(0,0)=1,\qquad C_4(0,1)=1,\qquad C_4(1,0)=1,\qquad C_4(-1,0)=1.$$
عند \(m=2\) نكوّن ازواجا مرتبة من هذه القيم الاربع، ثم نحتفظ فقط بالمجاميع التي تحقق \(D>0\)، او تحقق \(D=0\) مع nimber غير صفري. الازواج المعدودة هي
$$ (1,1),\ (1,0),\ (0,1),\ (1,\ast 1),\ (\ast 1,1),\ (0,\ast 1),\ (\ast 1,0). $$
وعددها يساوي 7 تماما، وهو ما يطابق نقطة الفحص الصغيرة المستعملة في التطبيقات. هذا المثال الصغير يعرض بنية الخوارزمية كاملة: بناء الفهرس المحلي، ثم الدمج عبر \((D,X)\)، ثم تطبيق قاعدة الايجابية في النهاية.
تقوم تطبيقات C++ و Python و Java اولا بتعداد جميع الثلاثيات الصالحة \((a,b,g)\) وتجميع تكراراتها في الجدول \(C_w(d,g)\). ولتسهيل الفهرسة داخل المصفوفات، يحجز التنفيذ مجالا للفروق الموقعة اوسع قليلا من المجال الرياضي الفعلي. وتستعمل الفكرة نفسها لاحقا على محور المجاميع الكلية، بحيث يمكن تخزين كل قيمة ممكنة لـ \(D\) بواسطة ازاحة ثابتة.
يبدا توزيع الحالات من الحالة الفارغة \((D,X)=(0,0)\). وفي كل واحدة من الجولات \(m\)، يتم تحويل جميع صفوف xor، ثم يدمج الجدول المحلي المحول مع جدول الحالات المحول بصورة مستقلة عبر الترددات 64، وبعد ذلك يعيد تحويل Walsh-Hadamard العكسي النتيجة الى فضاء xor الاصلي. العلاقة نفسها تستخدم في اللغات الثلاث. وتزيد نسخة C++ فقط بعمل موازاة على حلقات الترددات المستقلة، من دون اي تغيير في الرياضيات.
بعد الجولة الاخيرة، يمثل كل صف قيمة كلية ممكنة لـ \(D\). ومجموع الصف هو \(\sum_X P_m(D,X)\). الصفوف التي تحقق \(D>0\) تضاف كلها. اما الصف الوحيد الذي يحقق \(D=0\)، فتزال منه الخانة ذات xor صفر. وبهذا تنفذ الصيغة السابقة لـ \(R(m,w)\) بدقة.
بناء الفهرس المحلي يحتاج زمنا \(O(w^3)\)، لان الثلاثيات الصالحة \((a,b,g)\) تعد صراحة. اما البرمجة الديناميكية بعد التحويل فتستخدم جدولا محليا للفروق فيه \(2w-3\) صفوف محجوزة، وجدولا كليا للمجاميع فيه \(2m(w-2)+1\) صفوف محجوزة، وكل صف يحتوي 64 حالة xor.
وفي كل جولة من الجولات \(m\)، تنفذ تحويلات Walsh-Hadamard على جميع الصفوف الكلية، ثم 64 عملية التفاف عادي مع الجدول المحلي. لذلك يكون الزمن الكلي
$$O\bigl(w^3+m(2m(w-2)+1)\cdot 64\log 64+m(2m(w-2)+1)(2w-3)\cdot 64\bigr).$$
اما الذاكرة فهي خطية في عدد الحالات المخزنة:
$$O\bigl((2m(w-2)+1+2w-3)\cdot 64\bigr).$$
وبما ان بعد xor ثابت ويساوي 64 في المسألة الفعلية، فان النمو العملي تحكمه اساسا سعة محور المجاميع الموقعة، لا انفجارا اسيا في عدد اوضاع Young.