The quantity \(C(n,s)\) counts losing positions in the card-stacking game with \(s\) independent suits and \(n\) cards per suit. The real target is \(C(10^7,10^7)\) modulo \(M=10^9+7\), so brute force is impossible. The implementation therefore does not enumerate positions directly: it first computes the Grundy-value distribution for a single suit, then combines \(s\) identical suit distributions by xor convolution.
Let \(a_g\) be the number of one-suit positions whose Grundy value is \(g\). The implementation shows that only \(0\le g\le n-1\) occur, and that these frequencies partition all one-suit states:
$$\sum_{g=0}^{n-1} a_g = 2^n.$$
Once this one-suit distribution is known, the multi-suit count follows from standard impartial-game xor rules.
If the \(j\)-th suit contributes Grundy value \(x_j\), then the total position has value
$$x_1\oplus x_2\oplus \cdots \oplus x_s.$$
A position is losing exactly when this xor is \(0\). Therefore
$$C(n,s)=\sum_{x_1\oplus\cdots\oplus x_s=0}\prod_{j=1}^{s} a_{x_j}.$$
This formula says that the whole problem is controlled by the frequency table \(a_g\) for one suit.
The one-suit distribution is generated by a recurrence indexed by \(m=\lfloor g/2\rfloor\). After simplifying the ratio updates used by the implementation, the auxiliary quantities become ordinary binomial coefficients:
$$\beta_m=\binom{n-m-2}{m},\qquad \alpha_m=\begin{cases} 0,&m=0,\\ \binom{n-m-2}{m-1},&m\ge 1. \end{cases}$$
Applying Pascal's identity gives two more useful expressions:
$$\pi_m=\alpha_m+\beta_m=\binom{n-m-1}{m},$$
$$\chi_m=\pi_m\frac{n-2m-1}{m+1}=\binom{n-m-1}{m+1}.$$
The power-of-two baseline that appears in the code starts at \(2^{n-2}\) and is halved at every step, so at stage \(m\) it is exactly
$$2^{n-2-m}.$$
The remaining correction term is another linear recurrence:
$$\tau_0=1,\qquad \tau_{m+1}=\frac{\tau_m+\alpha_{m+1}}{2}+\beta_{m+1}.$$
With this notation the one-suit frequencies are
$$a_0=2^{n-2}+2,$$
$$a_{2m+1}=2^{n-2-m}+\chi_m-\tau_m \qquad \left(0\le m\le \left\lfloor\frac{n-2}{2}\right\rfloor\right),$$
$$a_{2m}=2^{n-2-m}+\pi_m+\beta_m-\tau_m \qquad \left(1\le m\le \left\lfloor\frac{n-1}{2}\right\rfloor\right).$$
This produces every nonzero \(a_g\) in \(O(n)\) time, without traversing any of the \(2^n\) one-suit states individually.
The implementation verifies two identities that are mathematically informative and computationally useful:
$$\sum_{g=0}^{n-1} a_g = 2^n,$$
$$a_{n-1}=1.$$
The first identity confirms that the recurrence accounts for every one-suit position exactly once. The second shows that the largest attainable Grundy value appears exactly once. Both checks are strong consistency tests before the xor-convolution stage starts.
For arrays \(f\) and \(g\), define xor convolution by
$$ (f *_\oplus g)(t)=\sum_{x\oplus y=t} f(x)g(y). $$
Then \(C(n,s)\) is the coefficient at \(t=0\) of the \(s\)-fold xor convolution of the one-suit distribution with itself. Let
$$P=2^{\lceil \log_2 n\rceil}.$$
Pad \((a_0,\dots,a_{n-1})\) with zeros to length \(P\), apply the Walsh-Hadamard transform, and write the transformed vector as \(\widehat{a}\). The xor-convolution theorem yields
$$C(n,s)=\frac{1}{P}\sum_{i=0}^{P-1}\widehat{a}_i^s \pmod{M},\qquad M=10^9+7.$$
So the \(s\)-suit aggregation becomes a pointwise power in transform space.
For one suit, the base value is
$$a_0=2^{1}+2=4.$$
At \(m=0\), we have \(\beta_0=1\), \(\alpha_0=0\), \(\pi_0=1\), \(\chi_0=2\), and \(\tau_0=1\). Therefore
$$a_1=2^1+\chi_0-\tau_0=2+2-1=3.$$
Next, \(\alpha_1=1\) and \(\beta_1=0\), so
$$\tau_1=\frac{1+1}{2}+0=1,$$
and hence
$$a_2=2^0+\pi_1+\beta_1-\tau_1=1+1+0-1=1.$$
Thus the one-suit distribution is
$$a=(4,3,1).$$
Pad it to \(P=4\):
$$a=(4,3,1,0).$$
Its Walsh-Hadamard transform is
$$\widehat{a}=(8,2,6,0).$$
For two suits, the losing count is
$$C(3,2)=\frac{8^2+2^2+6^2+0^2}{4}=26,$$
which matches the checkpoint used by the implementation.
The C++, Python, and Java implementations all follow the same mathematics. They first precompute modular inverses up to \(n\), so that every rational-looking factor in the recurrence can be evaluated modulo \(10^9+7\). They then run one forward pass over \(m\), updating the auxiliary sequences and filling the one-suit frequency table for all Grundy values below \(n\).
After that, the distribution is padded to the next power of two and transformed in place with the Walsh-Hadamard transform. In the transformed domain, each spectral entry is raised to the \(s\)-th power, the results are summed, and the final multiplication by \(P^{-1}\) extracts the zero-xor coefficient. The C++ and Java implementations also parallelize the large transform and exponentiation loops on big inputs, while the Python implementation delegates to the same compiled arithmetic core, so all three language versions evaluate the same recurrence and the same transform formula.
Building the modular inverses and the one-suit distribution costs \(O(n)\) time and \(O(n)\) memory before padding. Let \(P=2^{\lceil\log_2 n\rceil}\), so \(n\le P<2n\). The Walsh-Hadamard transform costs \(O(P\log P)\), and exponentiating all transformed entries to the \(s\)-th power costs \(O(P\log s)\). Therefore the total running time is \(O(n + P\log P + P\log s)\), which is effectively \(O(n\log n + n\log s)\), and the working memory is \(O(P)\).
Die gesuchte Größe \(C(n,s)\) zählt verlorene Positionen im Card-Stacking-Game mit \(s\) unabhängigen Farben und \(n\) Karten pro Farbe. Die eigentliche Zielgröße ist \(C(10^7,10^7)\) modulo \(M=10^9+7\), daher ist jede direkte Enumeration ausgeschlossen. Die Implementierung zählt deshalb nicht die Stellungen selbst, sondern berechnet zuerst die Grundy-Wert-Verteilung für eine einzelne Farbe und kombiniert dann \(s\) identische Verteilungen per XOR-Faltung.
Sei \(a_g\) die Anzahl der Ein-Farben-Stellungen mit Grundy-Wert \(g\). Aus der Implementierung liest man ab, dass nur \(0\le g\le n-1\) auftreten und dass diese Häufigkeiten alle Ein-Farben-Stellungen vollständig zerlegen:
$$\sum_{g=0}^{n-1} a_g = 2^n.$$
Sobald diese Verteilung bekannt ist, folgt der Mehrfarben-Fall direkt aus den XOR-Regeln der Theorie unparteiischer Spiele.
Liefert die \(j\)-te Farbe den Grundy-Wert \(x_j\), dann besitzt die Gesamtstellung den Wert
$$x_1\oplus x_2\oplus \cdots \oplus x_s.$$
Eine Stellung ist genau dann verloren, wenn dieses XOR gleich \(0\) ist. Daher gilt
$$C(n,s)=\sum_{x_1\oplus\cdots\oplus x_s=0}\prod_{j=1}^{s} a_{x_j}.$$
Damit hängt das gesamte Problem nur noch von der Häufigkeitstabelle \(a_g\) einer einzigen Farbe ab.
Die Ein-Farben-Verteilung wird über einen Index \(m=\lfloor g/2\rfloor\) aufgebaut. Vereinfacht man die in der Implementierung verwendeten Quotienten, erscheinen die Hilfsgrößen als gewöhnliche Binomialkoeffizienten:
$$\beta_m=\binom{n-m-2}{m},\qquad \alpha_m=\begin{cases} 0,&m=0,\\ \binom{n-m-2}{m-1},&m\ge 1. \end{cases}$$
Mit Pascalscher Identität erhält man außerdem
$$\pi_m=\alpha_m+\beta_m=\binom{n-m-1}{m},$$
$$\chi_m=\pi_m\frac{n-2m-1}{m+1}=\binom{n-m-1}{m+1}.$$
Der Zweierpotenz-Anteil startet bei \(2^{n-2}\) und wird in jedem Schritt halbiert; in Stufe \(m\) ist er also
$$2^{n-2-m}.$$
Übrig bleibt eine weitere lineare Korrekturfolge:
$$\tau_0=1,\qquad \tau_{m+1}=\frac{\tau_m+\alpha_{m+1}}{2}+\beta_{m+1}.$$
Damit lauten die Häufigkeiten
$$a_0=2^{n-2}+2,$$
$$a_{2m+1}=2^{n-2-m}+\chi_m-\tau_m \qquad \left(0\le m\le \left\lfloor\frac{n-2}{2}\right\rfloor\right),$$
$$a_{2m}=2^{n-2-m}+\pi_m+\beta_m-\tau_m \qquad \left(1\le m\le \left\lfloor\frac{n-1}{2}\right\rfloor\right).$$
So entstehen alle nichtverschwindenden \(a_g\) in \(O(n)\) Zeit, ohne die \(2^n\) Ein-Farben-Stellungen einzeln zu durchlaufen.
Die Implementierung überprüft zwei Identitäten, die sowohl mathematisch aufschlussreich als auch praktisch hilfreich sind:
$$\sum_{g=0}^{n-1} a_g = 2^n,$$
$$a_{n-1}=1.$$
Die erste Identität bestätigt, dass die Rekurrenz jede Ein-Farben-Stellung genau einmal erfasst. Die zweite zeigt, dass der größte erreichbare Grundy-Wert genau einmal vorkommt. Beides sind starke Konsistenztests vor der XOR-Faltung.
Für Felder \(f\) und \(g\) definieren wir die XOR-Faltung durch
$$ (f *_\oplus g)(t)=\sum_{x\oplus y=t} f(x)g(y). $$
Dann ist \(C(n,s)\) genau der Koeffizient bei \(t=0\) der \(s\)-fachen XOR-Faltung der Ein-Farben-Verteilung mit sich selbst. Sei
$$P=2^{\lceil \log_2 n\rceil}.$$
Man ergänzt \((a_0,\dots,a_{n-1})\) mit Nullen auf Länge \(P\), wendet die Walsh-Hadamard-Transformation an und bezeichnet den transformierten Vektor mit \(\widehat{a}\). Aus dem XOR-Faltungssatz folgt
$$C(n,s)=\frac{1}{P}\sum_{i=0}^{P-1}\widehat{a}_i^s \pmod{M},\qquad M=10^9+7.$$
Damit wird die Aggregation über \(s\) Farben im Transformationsraum zu einer komponentenweisen Potenzierung.
Für eine Farbe gilt zunächst
$$a_0=2^{1}+2=4.$$
Bei \(m=0\) haben wir \(\beta_0=1\), \(\alpha_0=0\), \(\pi_0=1\), \(\chi_0=2\) und \(\tau_0=1\). Also
$$a_1=2^1+\chi_0-\tau_0=2+2-1=3.$$
Dann ist \(\alpha_1=1\) und \(\beta_1=0\), somit
$$\tau_1=\frac{1+1}{2}+0=1,$$
und daraus folgt
$$a_2=2^0+\pi_1+\beta_1-\tau_1=1+1+0-1=1.$$
Die Ein-Farben-Verteilung lautet also
$$a=(4,3,1).$$
Mit Auffüllen auf \(P=4\) erhält man
$$a=(4,3,1,0).$$
Die Walsh-Hadamard-Transformation ist
$$\widehat{a}=(8,2,6,0).$$
Für zwei Farben ergibt sich deshalb
$$C(3,2)=\frac{8^2+2^2+6^2+0^2}{4}=26,$$
genau der Kontrollwert aus der Implementierung.
Die C++-, Python- und Java-Implementierungen folgen alle derselben Mathematik. Zuerst werden modulare Inversen bis \(n\) vorbereitet, damit jede bruchartige Größe in der Rekurrenz modulo \(10^9+7\) ausgewertet werden kann. Danach läuft ein einziger Vorwärtsdurchgang über \(m\), der die Hilfsfolgen aktualisiert und die Ein-Farben-Häufigkeitstabelle für alle Grundy-Werte unterhalb von \(n\) füllt.
Anschließend wird die Verteilung auf die nächste Zweierpotenz aufgefüllt und in place mit der Walsh-Hadamard-Transformation transformiert. Im Spektralraum wird jede Komponente in die \(s\)-te Potenz erhoben, alles wird aufsummiert, und die abschließende Multiplikation mit \(P^{-1}\) liefert den Koeffizienten zum XOR-Wert \(0\). Die C++- und Java-Versionen parallelisieren dabei die großen Transformations- und Potenzierungsschleifen, während die Python-Version denselben kompilierten Rechenkern nutzt; dadurch berechnen alle drei Sprachen dieselbe Rekurrenz und dieselbe Transformationsformel.
Der Aufbau der modularen Inversen und der Ein-Farben-Verteilung kostet \(O(n)\) Zeit und \(O(n)\) Speicher vor dem Auffüllen. Mit \(P=2^{\lceil\log_2 n\rceil}\) gilt \(n\le P<2n\). Die Walsh-Hadamard-Transformation benötigt \(O(P\log P)\), und das Potenzieren aller Spektraleinträge zur \(s\)-ten Potenz kostet \(O(P\log s)\). Insgesamt erhält man also \(O(n + P\log P + P\log s)\), praktisch also \(O(n\log n + n\log s)\), bei \(O(P)\) Arbeitsspeicher.
\(C(n,s)\) buyuklugu, \(s\) bagimsiz maza ve her mazada \(n\) kart bulunan Card Stacking Game icin kaybeden konumlarin sayisini verir. Asil hedef \(C(10^7,10^7)\) degerini \(M=10^9+7\) modunda bulmaktir; bu yuzden dogrudan sayma mumkun degildir. Uygulama bu nedenle konumlari tek tek gezmez; once tek bir mazanin Grundy deger dagilimini cikarir, sonra da birbirinin ayni \(s\) dagilimi xor konvolusyonu ile birlestirir.
\(a_g\), tek maza icindeki Grundy degeri \(g\) olan konumlarin sayisi olsun. Uygulama iki temel olguyu gosterir: yalnizca \(0\le g\le n-1\) degerleri ortaya cikar ve bu frekanslar tek maza durumlarinin tamaminin bir parcasi degil, tamamidir:
$$\sum_{g=0}^{n-1} a_g = 2^n.$$
Bu dagilim elde edildikten sonra coklu maza problemi, tarafsiz oyunlarin standart xor kuralina indirgenir.
\(j\). maza \(x_j\) Grundy degeri uretiyorsa toplam konumun degeri
$$x_1\oplus x_2\oplus \cdots \oplus x_s$$
olur. Bu xor degeri \(0\) ise konum kaybedendir. Dolayisiyla
$$C(n,s)=\sum_{x_1\oplus\cdots\oplus x_s=0}\prod_{j=1}^{s} a_{x_j}.$$
Boylece butun problem tek bir maza icin olusan \(a_g\) tablosuna baglanir.
Tek maza dagilimi \(m=\lfloor g/2\rfloor\) indisiyle kurulan bir rekursif duzen uzerinden uretilir. Uygulamadaki oran guncellemeleri sadelestirildiginde yardimci terimler normal binom katsayilarina donusur:
$$\beta_m=\binom{n-m-2}{m},\qquad \alpha_m=\begin{cases} 0,&m=0,\\ \binom{n-m-2}{m-1},&m\ge 1. \end{cases}$$
Pascal ozdesligi ile iki yararli ifade daha elde edilir:
$$\pi_m=\alpha_m+\beta_m=\binom{n-m-1}{m},$$
$$\chi_m=\pi_m\frac{n-2m-1}{m+1}=\binom{n-m-1}{m+1}.$$
Koddaki iki kuvveti tabani \(2^{n-2}\) ile baslar ve her adimda ikiye bolunur; dolayisiyla \(m\). asamada degeri
$$2^{n-2-m}$$
olur.
Geriye kalan duzeltme terimi de lineer bir rekuranstir:
$$\tau_0=1,\qquad \tau_{m+1}=\frac{\tau_m+\alpha_{m+1}}{2}+\beta_{m+1}.$$
Bu gosteri ile frekanslar
$$a_0=2^{n-2}+2,$$
$$a_{2m+1}=2^{n-2-m}+\chi_m-\tau_m \qquad \left(0\le m\le \left\lfloor\frac{n-2}{2}\right\rfloor\right),$$
$$a_{2m}=2^{n-2-m}+\pi_m+\beta_m-\tau_m \qquad \left(1\le m\le \left\lfloor\frac{n-1}{2}\right\rfloor\right)$$
seklindedir. Boylece sifirdan farkli tum \(a_g\) degerleri \(O(n)\) zamanda hesaplanir; tek maza icindeki \(2^n\) durumun hicbiri tek tek ziyaret edilmez.
Uygulama, matematiksel olarak anlamli ve sayisal olarak koruyucu iki ozdesligi denetler:
$$\sum_{g=0}^{n-1} a_g = 2^n,$$
$$a_{n-1}=1.$$
Birinci ozdeslik rekursiyonun her tek maza konumunu tam bir kez saydigini gosterir. Ikinci ozdeslik ise ulasilabilen en buyuk Grundy degerinin yalnizca bir kez ortaya ciktigini soyler. Xor konvolusyonuna gecmeden once bunlar cok guclu tutarlilik testleridir.
\(f\) ve \(g\) dizileri icin xor konvolusyonu
$$ (f *_\oplus g)(t)=\sum_{x\oplus y=t} f(x)g(y) $$
olarak tanimlayalim. O zaman \(C(n,s)\), tek maza dagiliminin kendisiyle alinmis \(s\) katli xor konvolusyonunda \(t=0\) katsayisidir. Simdi
$$P=2^{\lceil \log_2 n\rceil}$$
olsun. \((a_0,\dots,a_{n-1})\) dizisini uzunlugu \(P\) olacak sekilde sifirlarla doldurup Walsh-Hadamard donusumunu uygularsak ve donusmus vektoru \(\widehat{a}\) ile gosterirsek, xor-konvolusyon teoremi bize
$$C(n,s)=\frac{1}{P}\sum_{i=0}^{P-1}\widehat{a}_i^s \pmod{M},\qquad M=10^9+7$$
formulunu verir. Boylece \(s\) mazanin birlesimi donusum uzayinda bilesen bazli us almaya iner.
Tek maza icin taban deger
$$a_0=2^{1}+2=4$$
olur. \(m=0\) icin \(\beta_0=1\), \(\alpha_0=0\), \(\pi_0=1\), \(\chi_0=2\) ve \(\tau_0=1\) oldugundan
$$a_1=2^1+\chi_0-\tau_0=2+2-1=3.$$
Sonra \(\alpha_1=1\) ve \(\beta_1=0\), dolayisiyla
$$\tau_1=\frac{1+1}{2}+0=1,$$
ve buradan
$$a_2=2^0+\pi_1+\beta_1-\tau_1=1+1+0-1=1$$
elde edilir. Demek ki tek maza dagilimi
$$a=(4,3,1)$$
olur. Bunu \(P=4\) uzunluguna sifirla tamamlayinca
$$a=(4,3,1,0)$$
elde edilir. Walsh-Hadamard donusumu
$$\widehat{a}=(8,2,6,0)$$
oldugundan iki maza icin kaybeden konum sayisi
$$C(3,2)=\frac{8^2+2^2+6^2+0^2}{4}=26$$
cikar; bu da uygulamadaki kontrol degeriyle aynidir.
C++, Python ve Java uygulamalari ayni matematigi izler. Once \(n\)'e kadar moduler tersler hazirlanir; boylece rekuranstaki kesirli gorunen her carpim \(10^9+7\) modunda guvenle hesaplanir. Sonra \(m\) uzerinden tek bir ileri gecis yapilarak yardimci diziler guncellenir ve \(n\)'den kucuk tum Grundy degerleri icin tek maza frekans tablosu doldurulur.
Ardindan dagilim bir sonraki iki kuvvetine kadar sifirla tamamlanir ve yerinde Walsh-Hadamard donusumu uygulanir. Donusum uzayinda her spektral bilesen \(s\). kuvvete yukseltilir, bunlar toplanir ve son olarak \(P^{-1}\) ile carpilarak xor degeri \(0\) olan katsayi geri kazanilir. C++ ve Java surumleri buyuk girdilerde donusum ve us alma dongulerini cok cekirdege paylastirir; Python surumu ise ayni derlenmis aritmetik cekirdege delege eder. Bu nedenle uc dil de ayni rekuransi ve ayni donusum formulunu hesaplar.
Moduler terslerin ve tek maza dagiliminin kurulmasi, sifirla tamamlama oncesinde \(O(n)\) zaman ve \(O(n)\) bellek ister. \(P=2^{\lceil\log_2 n\rceil}\) icin \(n\le P<2n\) olur. Walsh-Hadamard donusumu \(O(P\log P)\), donusmus tum bilesenlerin \(s\). kuvvetini hizli us alma ile hesaplamak ise \(O(P\log s)\) maliyetindedir. Sonuc olarak toplam sure \(O(n + P\log P + P\log s)\), yani pratikte \(O(n\log n + n\log s)\), bellek ise \(O(P)\) olur.
La cantidad \(C(n,s)\) cuenta las posiciones perdedoras del juego Card Stacking Game con \(s\) palos independientes y \(n\) cartas por palo. El objetivo real es \(C(10^7,10^7)\) modulo \(M=10^9+7\), asi que una enumeracion directa es inviable. Por eso la implementacion no recorre las posiciones una por una: primero calcula la distribucion de valores de Grundy para un solo palo y despues combina \(s\) copias identicas mediante convolucion xor.
Sea \(a_g\) el numero de posiciones de un solo palo cuyo valor de Grundy es \(g\). La implementacion muestra que solo aparecen \(0\le g\le n-1\), y que estas frecuencias cubren exactamente todos los estados de un palo:
$$\sum_{g=0}^{n-1} a_g = 2^n.$$
Una vez conocida esta distribucion, el caso con varios palos se resuelve con la regla xor habitual de los juegos imparciales.
Si el palo \(j\) aporta valor de Grundy \(x_j\), entonces la posicion total tiene valor
$$x_1\oplus x_2\oplus \cdots \oplus x_s.$$
Una posicion es perdedora exactamente cuando ese xor vale \(0\). Por tanto,
$$C(n,s)=\sum_{x_1\oplus\cdots\oplus x_s=0}\prod_{j=1}^{s} a_{x_j}.$$
Asi, todo el problema queda controlado por la tabla de frecuencias \(a_g\) de un unico palo.
La distribucion de un palo se genera con una recurrencia indexada por \(m=\lfloor g/2\rfloor\). Al simplificar los cocientes de actualizacion que usa la implementacion, las cantidades auxiliares se convierten en coeficientes binomiales ordinarios:
$$\beta_m=\binom{n-m-2}{m},\qquad \alpha_m=\begin{cases} 0,&m=0,\\ \binom{n-m-2}{m-1},&m\ge 1. \end{cases}$$
Usando la identidad de Pascal se obtienen dos expresiones mas:
$$\pi_m=\alpha_m+\beta_m=\binom{n-m-1}{m},$$
$$\chi_m=\pi_m\frac{n-2m-1}{m+1}=\binom{n-m-1}{m+1}.$$
El termino base en potencias de dos empieza en \(2^{n-2}\) y se divide entre \(2\) en cada paso; en la etapa \(m\) vale exactamente
$$2^{n-2-m}.$$
Queda una sucesion de correccion, tambien lineal:
$$\tau_0=1,\qquad \tau_{m+1}=\frac{\tau_m+\alpha_{m+1}}{2}+\beta_{m+1}.$$
Con esa notacion, las frecuencias son
$$a_0=2^{n-2}+2,$$
$$a_{2m+1}=2^{n-2-m}+\chi_m-\tau_m \qquad \left(0\le m\le \left\lfloor\frac{n-2}{2}\right\rfloor\right),$$
$$a_{2m}=2^{n-2-m}+\pi_m+\beta_m-\tau_m \qquad \left(1\le m\le \left\lfloor\frac{n-1}{2}\right\rfloor\right).$$
Esto produce todos los \(a_g\) no nulos en tiempo \(O(n)\), sin visitar individualmente ninguno de los \(2^n\) estados de un solo palo.
La implementacion verifica dos identidades que son utiles tanto matematicamente como desde el punto de vista computacional:
$$\sum_{g=0}^{n-1} a_g = 2^n,$$
$$a_{n-1}=1.$$
La primera confirma que la recurrencia reparte todos los estados de un palo sin omisiones ni duplicados. La segunda muestra que el mayor valor de Grundy alcanzable aparece exactamente una vez. Ambas sirven como controles fuertes antes de pasar a la convolucion xor.
Para arreglos \(f\) y \(g\), definimos la convolucion xor por
$$ (f *_\oplus g)(t)=\sum_{x\oplus y=t} f(x)g(y). $$
Entonces \(C(n,s)\) es precisamente el coeficiente con \(t=0\) en la \(s\)-esima convolucion xor de la distribucion de un palo consigo misma. Sea
$$P=2^{\lceil \log_2 n\rceil}.$$
Rellenamos \((a_0,\dots,a_{n-1})\) con ceros hasta longitud \(P\), aplicamos la transformada de Walsh-Hadamard y llamamos \(\widehat{a}\) al vector transformado. El teorema de convolucion xor da
$$C(n,s)=\frac{1}{P}\sum_{i=0}^{P-1}\widehat{a}_i^s \pmod{M},\qquad M=10^9+7.$$
Asi, la agregacion de \(s\) palos se convierte en elevar componente a componente dentro del espacio transformado.
Para un palo, el valor base es
$$a_0=2^{1}+2=4.$$
En \(m=0\) tenemos \(\beta_0=1\), \(\alpha_0=0\), \(\pi_0=1\), \(\chi_0=2\) y \(\tau_0=1\). Por tanto,
$$a_1=2^1+\chi_0-\tau_0=2+2-1=3.$$
Despues, \(\alpha_1=1\) y \(\beta_1=0\), de modo que
$$\tau_1=\frac{1+1}{2}+0=1,$$
y entonces
$$a_2=2^0+\pi_1+\beta_1-\tau_1=1+1+0-1=1.$$
La distribucion de un palo queda
$$a=(4,3,1).$$
Rellenando hasta \(P=4\):
$$a=(4,3,1,0).$$
Su transformada de Walsh-Hadamard es
$$\widehat{a}=(8,2,6,0).$$
Para dos palos, el numero de posiciones perdedoras es
$$C(3,2)=\frac{8^2+2^2+6^2+0^2}{4}=26,$$
que coincide con el valor de control de la implementacion.
Las implementaciones en C++, Python y Java siguen exactamente la misma matematica. Primero precalculan inversos modulares hasta \(n\), de modo que cada factor racional de la recurrencia puede evaluarse modulo \(10^9+7\). Luego hacen una sola pasada hacia adelante sobre \(m\), actualizando las sucesiones auxiliares y llenando la tabla de frecuencias de un solo palo para todos los valores de Grundy menores que \(n\).
Despues, la distribucion se amplia hasta la siguiente potencia de dos y se transforma in situ con Walsh-Hadamard. En el dominio transformado, cada componente espectral se eleva a la potencia \(s\), se suman todas esas contribuciones y la multiplicacion final por \(P^{-1}\) recupera el coeficiente con xor igual a \(0\). Las versiones en C++ y Java paralelizan los bucles mas pesados de transformacion y exponenciacion cuando la entrada es grande, mientras que la version en Python delega en el mismo nucleo aritmetico compilado; por eso las tres versiones calculan la misma recurrencia y la misma formula transformada.
Construir los inversos modulares y la distribucion de un palo cuesta \(O(n)\) tiempo y \(O(n)\) memoria antes del relleno. Si \(P=2^{\lceil\log_2 n\rceil}\), entonces \(n\le P<2n\). La transformada de Walsh-Hadamard cuesta \(O(P\log P)\), y elevar todas las entradas transformadas a la potencia \(s\) mediante exponenciacion rapida cuesta \(O(P\log s)\). En consecuencia, el tiempo total es \(O(n + P\log P + P\log s)\), es decir, en la practica \(O(n\log n + n\log s)\), y la memoria de trabajo es \(O(P)\).
\(C(n,s)\) 统计的是 Card Stacking Game 中的必败局面数目，其中有 \(s\) 个彼此独立的花色，每个花色有 \(n\) 张牌。真正需要求的是 \(C(10^7,10^7)\bmod M\)，这里 \(M=10^9+7\)。规模如此之大，当然不可能直接枚举局面，所以实现采用两层结构：先求单一花色的 Grundy 值分布，再把这份分布通过 xor 卷积合并 \(s\) 次。
设 \(a_g\) 表示单一花色中 Grundy 值恰好为 \(g\) 的局面数。实现清楚地表明：只有 \(0\le g\le n-1\) 会出现，而且这些频数恰好覆盖全部单花色局面：
$$\sum_{g=0}^{n-1} a_g = 2^n.$$
一旦单花色分布求出，多花色情形就可以直接交给 Sprague-Grundy 理论中的 xor 规则。
如果第 \(j\) 个花色贡献的 Grundy 值是 \(x_j\)，那么整个局面的 Grundy 值就是
$$x_1\oplus x_2\oplus \cdots \oplus x_s.$$
在无偏博弈里，xor 和为 \(0\) 当且仅当该局面对当前玩家是必败局面。因此
$$C(n,s)=\sum_{x_1\oplus\cdots\oplus x_s=0}\prod_{j=1}^{s} a_{x_j}.$$
这一步的意义非常关键：原问题不再需要研究完整的大局面，只需要知道“一个花色会产生哪些 Grundy 值、各自出现多少次”。
单花色分布是按 \(m=\lfloor g/2\rfloor\) 这个层级来递推生成的。把实现中的比值更新式整理之后，可以看出辅助量本质上就是普通的二项式系数：
$$\beta_m=\binom{n-m-2}{m},\qquad \alpha_m=\begin{cases} 0,&m=0,\\ \binom{n-m-2}{m-1},&m\ge 1. \end{cases}$$
再利用 Pascal 恒等式，可以得到另外两个更紧凑的表达式：
$$\pi_m=\alpha_m+\beta_m=\binom{n-m-1}{m},$$
$$\chi_m=\pi_m\frac{n-2m-1}{m+1}=\binom{n-m-1}{m+1}.$$
实现里还有一个不断减半的 \(2\) 的幂次基线。它从 \(2^{n-2}\) 开始，每前进一步就除以 \(2\)，所以在第 \(m\) 层时恰好是
$$2^{n-2-m}.$$
这样一来，程序中的“递推更新”就可以被解释成一组很规整的组合数量和一个简单的修正序列。
剩余的修正量满足另一条线性递推：
$$\tau_0=1,\qquad \tau_{m+1}=\frac{\tau_m+\alpha_{m+1}}{2}+\beta_{m+1}.$$
于是单花色频数可以写成
$$a_0=2^{n-2}+2,$$
$$a_{2m+1}=2^{n-2-m}+\chi_m-\tau_m \qquad \left(0\le m\le \left\lfloor\frac{n-2}{2}\right\rfloor\right),$$
$$a_{2m}=2^{n-2-m}+\pi_m+\beta_m-\tau_m \qquad \left(1\le m\le \left\lfloor\frac{n-1}{2}\right\rfloor\right).$$
这说明所有非零的 \(a_g\) 都能在线性时间内求出，完全不需要真的去枚举那 \(2^n\) 个单花色局面。换句话说，核心难点不在于“逐局面分析”，而在于识别出一个能压缩全部信息的递推结构。
实现还检查了两个非常有用的恒等式：
$$\sum_{g=0}^{n-1} a_g = 2^n,$$
$$a_{n-1}=1.$$
第一条说明单花色分布确实把所有局面精确分箱，没有遗漏也没有重复。第二条说明最大的可达 Grundy 值只出现一次。它们既是数学上的结构信息，也是实际程序中非常强的正确性检查，因为只要递推哪怕偏掉一点，这两条约束就往往立刻失效。
对两个数组 \(f\) 与 \(g\)，定义 xor 卷积为
$$ (f *_\oplus g)(t)=\sum_{x\oplus y=t} f(x)g(y). $$
那么 \(C(n,s)\) 正是单花色分布与自身做 \(s\) 次 xor 卷积后，在 \(t=0\) 位置上的系数。令
$$P=2^{\lceil \log_2 n\rceil}.$$
把 \((a_0,\dots,a_{n-1})\) 用零补到长度 \(P\)，再做 Walsh-Hadamard 变换，记变换后的向量为 \(\widehat{a}\)。由于 Walsh-Hadamard 变换可以把 xor 卷积对角化，于是有
$$C(n,s)=\frac{1}{P}\sum_{i=0}^{P-1}\widehat{a}_i^s \pmod{M},\qquad M=10^9+7.$$
这一步把原本看似复杂的“\(s\) 个花色一起合并”的问题，转化成频域里的逐点幂和求和。组合结构负责给出 \(a_g\)，快速变换负责把 \(s\) 次合并变成高效的代数操作。
先看单花色。基础项是
$$a_0=2^{1}+2=4.$$
当 \(m=0\) 时，\(\beta_0=1\)、\(\alpha_0=0\)、\(\pi_0=1\)、\(\chi_0=2\)、\(\tau_0=1\)，所以
$$a_1=2^1+\chi_0-\tau_0=2+2-1=3.$$
接着 \(\alpha_1=1\)、\(\beta_1=0\)，因此
$$\tau_1=\frac{1+1}{2}+0=1,$$
于是
$$a_2=2^0+\pi_1+\beta_1-\tau_1=1+1+0-1=1.$$
所以单花色分布为
$$a=(4,3,1).$$
为了做 Walsh-Hadamard 变换，把它补零到 \(P=4\)：
$$a=(4,3,1,0).$$
其变换结果是
$$\widehat{a}=(8,2,6,0).$$
对两个花色，只需把频域分量平方再求和并除以 \(4\)：
$$C(3,2)=\frac{8^2+2^2+6^2+0^2}{4}=26.$$
这正好与实现中的自检结果一致。这个小例子很好地展示了整套方法：先用递推求单花色分布，再用 Walsh-Hadamard 变换完成多花色合并。
C++、Python 和 Java 三个实现遵循的是同一套数学。首先会预处理 \(1\) 到 \(n\) 的模逆，从而把递推中看起来像分式的因子都安全地放到模 \(10^9+7\) 下计算。随后程序对 \(m\) 做一次线性扫描，更新辅助序列，并填出所有 \(g<n\) 的单花色频数；高于这个范围的位置保持为零，仅作为后续快速变换时的填充空间。
接下来，分布长度被扩展到不小于 \(n\) 的最小二次幂，然后原地执行 Walsh-Hadamard 变换。进入变换域后，每个谱值单独提升到 \(s\) 次方，再把这些结果累加起来，最后乘以 \(P^{-1}\) 取回 xor 为 \(0\) 的系数。C++ 与 Java 版本在大输入上还会并行化最重的变换循环和幂运算循环；Python 版本则把重计算委托给同一套编译后的算术核心，因此三种语言得到的分布和最终答案完全一致。
在补零之前，模逆预处理和单花色分布构造都需要 \(O(n)\) 时间与 \(O(n)\) 空间。设 \(P=2^{\lceil\log_2 n\rceil}\)，则 \(n\le P<2n\)。Walsh-Hadamard 变换的代价是 \(O(P\log P)\)，而把所有谱值用快速幂提升到 \(s\) 次方的代价是 \(O(P\log s)\)。因此总时间复杂度为 \(O(n + P\log P + P\log s)\)，也就是实质上的 \(O(n\log n + n\log s)\)，工作内存为 \(O(P)\)。
Величина \(C(n,s)\) считает проигрышные позиции в Card Stacking Game, где есть \(s\) независимых мастей и по \(n\) карт в каждой масти. Нужно найти \(C(10^7,10^7)\) по модулю \(M=10^9+7\), поэтому прямой перебор невозможен. Реализация решает задачу в два слоя: сначала строит распределение значений Гранди для одной масти, а затем объединяет \(s\) одинаковых распределений через xor-свертку.
Обозначим через \(a_g\) число позиций одной масти со значением Гранди \(g\). Из реализации видно, что встречаются только значения \(0\le g\le n-1\), и что эти частоты полностью разбивают все состояния одной масти:
$$\sum_{g=0}^{n-1} a_g = 2^n.$$
После этого многомастный случай полностью определяется xor-правилом теории беспристрастных игр.
Если \(j\)-я масть дает значение Гранди \(x_j\), то вся позиция имеет значение
$$x_1\oplus x_2\oplus \cdots \oplus x_s.$$
Позиция проигрышна тогда и только тогда, когда этот xor равен \(0\). Поэтому
$$C(n,s)=\sum_{x_1\oplus\cdots\oplus x_s=0}\prod_{j=1}^{s} a_{x_j}.$$
Тем самым вся задача сводится к таблице частот \(a_g\) для одной масти.
Распределение для одной масти строится по индексу \(m=\lfloor g/2\rfloor\). Если упростить отношения обновления из реализации, вспомогательные величины оказываются обычными биномиальными коэффициентами:
$$\beta_m=\binom{n-m-2}{m},\qquad \alpha_m=\begin{cases} 0,&m=0,\\ \binom{n-m-2}{m-1},&m\ge 1. \end{cases}$$
Из тождества Паскаля следуют еще две удобные формулы:
$$\pi_m=\alpha_m+\beta_m=\binom{n-m-1}{m},$$
$$\chi_m=\pi_m\frac{n-2m-1}{m+1}=\binom{n-m-1}{m+1}.$$
Степенной фон по основанию \(2\) стартует с \(2^{n-2}\) и на каждом шаге делится пополам, так что на шаге \(m\) он равен
$$2^{n-2-m}.$$
Остается корректирующая последовательность, тоже заданная линейной рекурсией:
$$\tau_0=1,\qquad \tau_{m+1}=\frac{\tau_m+\alpha_{m+1}}{2}+\beta_{m+1}.$$
Тогда частоты выражаются так:
$$a_0=2^{n-2}+2,$$
$$a_{2m+1}=2^{n-2-m}+\chi_m-\tau_m \qquad \left(0\le m\le \left\lfloor\frac{n-2}{2}\right\rfloor\right),$$
$$a_{2m}=2^{n-2-m}+\pi_m+\beta_m-\tau_m \qquad \left(1\le m\le \left\lfloor\frac{n-1}{2}\right\rfloor\right).$$
Все ненулевые \(a_g\) получаются за \(O(n)\) времени, без явного обхода \(2^n\) состояний одной масти.
Реализация дополнительно проверяет два тождества, которые важны и математически, и практически:
$$\sum_{g=0}^{n-1} a_g = 2^n,$$
$$a_{n-1}=1.$$
Первое гарантирует, что рекурсия распределяет все состояния одной масти без пропусков и повторного счета. Второе показывает, что максимальное достижимое значение Гранди встречается ровно один раз. Оба условия служат сильными проверками до перехода к xor-свертке.
Для массивов \(f\) и \(g\) определим xor-свертку:
$$ (f *_\oplus g)(t)=\sum_{x\oplus y=t} f(x)g(y). $$
Тогда \(C(n,s)\) есть коэффициент при \(t=0\) в \(s\)-кратной xor-свертке распределения одной масти с самим собой. Положим
$$P=2^{\lceil \log_2 n\rceil}.$$
Дополняем \((a_0,\dots,a_{n-1})\) нулями до длины \(P\), применяем преобразование Уолша-Хадамара и обозначаем полученный вектор через \(\widehat{a}\). Теорема о xor-свертке дает
$$C(n,s)=\frac{1}{P}\sum_{i=0}^{P-1}\widehat{a}_i^s \pmod{M},\qquad M=10^9+7.$$
Таким образом, объединение \(s\) мастей сводится к покомпонентному возведению в степень в пространстве преобразования.
Для одной масти сначала получаем
$$a_0=2^{1}+2=4.$$
При \(m=0\) имеем \(\beta_0=1\), \(\alpha_0=0\), \(\pi_0=1\), \(\chi_0=2\) и \(\tau_0=1\), поэтому
$$a_1=2^1+\chi_0-\tau_0=2+2-1=3.$$
Далее \(\alpha_1=1\), \(\beta_1=0\), значит
$$\tau_1=\frac{1+1}{2}+0=1,$$
и потому
$$a_2=2^0+\pi_1+\beta_1-\tau_1=1+1+0-1=1.$$
Итак, распределение одной масти равно
$$a=(4,3,1).$$
После дополнения до \(P=4\):
$$a=(4,3,1,0).$$
Преобразование Уолша-Хадамара дает
$$\widehat{a}=(8,2,6,0).$$
Для двух мастей получаем
$$C(3,2)=\frac{8^2+2^2+6^2+0^2}{4}=26,$$
что совпадает со значением встроенной проверки в реализации.
Реализации на C++, Python и Java следуют одной и той же математике. Сначала они предвычисляют модульные обратные до \(n\), чтобы все дробеподобные множители в рекурсии можно было корректно считать по модулю \(10^9+7\). Затем выполняется один линейный проход по \(m\), в ходе которого обновляются вспомогательные последовательности и заполняется таблица частот для всех значений Гранди меньше \(n\).
После этого распределение дополняется нулями до ближайшей степени двойки и преобразуется на месте с помощью Уолша-Хадамара. В спектральной области каждый компонент возводится в степень \(s\), затем все такие вклады суммируются, и финальное умножение на \(P^{-1}\) возвращает коэффициент при xor, равном \(0\). Версии на C++ и Java дополнительно распараллеливают самые тяжелые циклы преобразования и возведения в степень на больших входах, а версия на Python передает тяжелую арифметику тому же компилируемому ядру; поэтому все три версии вычисляют одну и ту же рекурсию и одну и ту же формулу после преобразования.
Построение модульных обратных и распределения одной масти требует \(O(n)\) времени и \(O(n)\) памяти до дополнения нулями. Если \(P=2^{\lceil\log_2 n\rceil}\), то \(n\le P<2n\). Преобразование Уолша-Хадамара стоит \(O(P\log P)\), а возведение всех спектральных коэффициентов в степень \(s\) быстрым методом стоит \(O(P\log s)\). Итого получаем \(O(n + P\log P + P\log s)\), то есть по существу \(O(n\log n + n\log s)\), при использовании \(O(P)\) памяти.
الكمية \(C(n,s)\) تعد المواضع الخاسرة في لعبة Card Stacking Game عندما يكون لدينا \(s\) انواع مستقلة من الالوان، وفي كل نوع \(n\) بطاقات. المطلوب الحقيقي هو حساب \(C(10^7,10^7)\) بترديد \(M=10^9+7\)، ولذلك فالتعداد المباشر مستحيل. لهذا السبب لا تقوم الخوارزمية بعد المواضع واحدا واحدا، بل تحسب اولا توزيع قيم Grundy للون واحد، ثم تدمج \(s\) نسخا متطابقة من هذا التوزيع بواسطة xor convolution.
لنرمز بـ \(a_g\) إلى عدد مواضع اللون الواحد التي تملك قيمة Grundy مساوية لـ \(g\). التنفيذ يبين امرين مهمين: القيم الممكنة تقع فقط في المجال \(0\le g\le n-1\)، كما ان هذه التكرارات تغطي جميع حالات اللون الواحد تماما:
$$\sum_{g=0}^{n-1} a_g = 2^n.$$
بعد معرفة هذا التوزيع، يصبح التعامل مع عدة الوان نتيجة مباشرة لقواعد xor في نظرية الالعاب غير المتحيزة.
اذا كانت قيمة Grundy التي يساهم بها اللون رقم \(j\) هي \(x_j\)، فقيمة الموضع الكامل تساوي
$$x_1\oplus x_2\oplus \cdots \oplus x_s.$$
ويكون الموضع خاسرا بالضبط عندما يكون xor الكلي صفرا. لذلك نحصل على
$$C(n,s)=\sum_{x_1\oplus\cdots\oplus x_s=0}\prod_{j=1}^{s} a_{x_j}.$$
وهذا يعني ان المسألة كلها تعتمد على جدول التكرارات \(a_g\) للون واحد فقط.
يتم بناء توزيع اللون الواحد عبر فهرس \(m=\lfloor g/2\rfloor\). وعندما نبسط نسب التحديث الموجودة في التنفيذ نجد ان الحدود المساعدة تتحول إلى معاملات ثنائية عادية:
$$\beta_m=\binom{n-m-2}{m},\qquad \alpha_m=\begin{cases} 0,&m=0,\\ \binom{n-m-2}{m-1},&m\ge 1. \end{cases}$$
وباستخدام هوية باسكال نحصل ايضا على
$$\pi_m=\alpha_m+\beta_m=\binom{n-m-1}{m},$$
$$\chi_m=\pi_m\frac{n-2m-1}{m+1}=\binom{n-m-1}{m+1}.$$
الجزء القائم على قوى العدد \(2\) يبدأ من \(2^{n-2}\) ثم ينقسم على \(2\) في كل خطوة، ولذلك ففي المرحلة \(m\) يكون مساويا تماما لـ
$$2^{n-2-m}.$$
يبقى لدينا حد تصحيحي يحقق ايضا علاقة خطية:
$$\tau_0=1,\qquad \tau_{m+1}=\frac{\tau_m+\alpha_{m+1}}{2}+\beta_{m+1}.$$
وبهذه الرموز تصبح التكرارات
$$a_0=2^{n-2}+2,$$
$$a_{2m+1}=2^{n-2-m}+\chi_m-\tau_m \qquad \left(0\le m\le \left\lfloor\frac{n-2}{2}\right\rfloor\right),$$
$$a_{2m}=2^{n-2-m}+\pi_m+\beta_m-\tau_m \qquad \left(1\le m\le \left\lfloor\frac{n-1}{2}\right\rfloor\right).$$
وهكذا نحصل على جميع القيم غير الصفرية لـ \(a_g\) في زمن \(O(n)\)، من غير المرور على \(2^n\) حالة منفردة للون الواحد.
التنفيذ يتحقق من هويتين لهما قيمة رياضية وعملية في الوقت نفسه:
$$\sum_{g=0}^{n-1} a_g = 2^n,$$
$$a_{n-1}=1.$$
الهوية الاولى تؤكد ان العلاقة التكرارية قسمت جميع حالات اللون الواحد من دون فقد او تكرار. والهوية الثانية تبين ان اكبر قيمة Grundy ممكنة تظهر مرة واحدة فقط. وهاتان العلاقتان توفران فحصا قويا قبل الانتقال إلى مرحلة xor convolution.
للمصفوفتين \(f\) و \(g\) نعرف xor convolution بالصيغة
$$ (f *_\oplus g)(t)=\sum_{x\oplus y=t} f(x)g(y). $$
عندئذ تكون \(C(n,s)\) هي المعامل عند \(t=0\) في xor convolution المتكرر \(s\) مرات لتوزيع اللون الواحد مع نفسه. لنكتب
$$P=2^{\lceil \log_2 n\rceil}.$$
نقوم بحشو \((a_0,\dots,a_{n-1})\) بالاصفار حتى الطول \(P\)، ثم نطبق تحويل Walsh-Hadamard ونرمز للمتجه الناتج بـ \(\widehat{a}\). عندها تعطينا نظرية xor convolution العلاقة
$$C(n,s)=\frac{1}{P}\sum_{i=0}^{P-1}\widehat{a}_i^s \pmod{M},\qquad M=10^9+7.$$
وبذلك تتحول عملية دمج \(s\) الوان من تركيب تركيبي معقد إلى رفع نقطي للقيم في فضاء التحويل.
بالنسبة إلى لون واحد، لدينا اولا
$$a_0=2^{1}+2=4.$$
وعند \(m=0\) تكون \(\beta_0=1\) و \(\alpha_0=0\) و \(\pi_0=1\) و \(\chi_0=2\) و \(\tau_0=1\)، ومن ثم
$$a_1=2^1+\chi_0-\tau_0=2+2-1=3.$$
بعد ذلك نجد \(\alpha_1=1\) و \(\beta_1=0\)، وبالتالي
$$\tau_1=\frac{1+1}{2}+0=1,$$
ومنها
$$a_2=2^0+\pi_1+\beta_1-\tau_1=1+1+0-1=1.$$
اذن توزيع اللون الواحد هو
$$a=(4,3,1).$$
وبعد الحشو حتى \(P=4\) نحصل على
$$a=(4,3,1,0).$$
وقيمة تحويل Walsh-Hadamard هي
$$\widehat{a}=(8,2,6,0).$$
للونين يصبح عدد المواضع الخاسرة
$$C(3,2)=\frac{8^2+2^2+6^2+0^2}{4}=26,$$
وهو تماما نفس مقدار الفحص الذاتي الموجود في التنفيذ.
تنفيذات C++ و Python و Java تتبع الرياضيات نفسها. في البداية يتم تجهيز المعكوسات المعيارية حتى \(n\)، بحيث يمكن تقييم كل عامل يبدو كسريا داخل العلاقة التكرارية تحت الترديد \(10^9+7\). بعد ذلك تنفذ الخوارزمية مسارا واحدا على \(m\)، تحدث خلاله المتتاليات المساعدة وتملأ جدول تكرارات اللون الواحد لكل قيم Grundy الاصغر من \(n\).
ثم يتم توسيع طول التوزيع إلى اصغر قوة للعدد \(2\) لا تقل عن \(n\)، ويطبق تحويل Walsh-Hadamard في المكان نفسه. في فضاء التحويل، ترفع كل قيمة طيفية إلى الاس \(s\)، ثم تجمع هذه القيم، واخيرا تضرب النتيجة في \(P^{-1}\) لاستعادة المعامل الموافق لـ xor يساوي \(0\). تنفيذي C++ و Java يوازيان الحلقات الثقيلة الخاصة بالتحويل ورفع القوى عندما تكبر المدخلات، اما تنفيذ Python فيفوض الحساب الثقيل إلى النواة العددية المترجمة نفسها، ولذلك تعطي اللغات الثلاث التوزيع نفسه والنتيجة النهائية نفسها.
بناء المعكوسات المعيارية وتوزيع اللون الواحد يحتاج إلى \(O(n)\) زمنا و \(O(n)\) ذاكرة قبل الحشو. اذا كان \(P=2^{\lceil\log_2 n\rceil}\) فلدينا \(n\le P<2n\). تحويل Walsh-Hadamard يكلف \(O(P\log P)\)، ورفع جميع القيم الطيفية إلى الاس \(s\) بالاس السريع يكلف \(O(P\log s)\). لذلك يكون الزمن الكلي \(O(n + P\log P + P\log s)\)، اي عمليا \(O(n\log n + n\log s)\)، بينما تبقى الذاكرة العاملة \(O(P)\).