Start from the congruential sequence
$$a_{n+1}\equiv 8888a_n \pmod{888888883},\qquad a_0=88888888,$$
and reduce each term modulo \(3\): \(b_n=a_n\bmod 3\). The residues \(0,1,2\) are read as the letters \(x,y,z\). The first \(50N\) letters are split into \(N\) consecutive blocks of length \(50\), and each block is interpreted as a word in the quaternion group \(Q_8=\{\pm1,\pm x,\pm y,\pm z\}\) with the standard relations \(x^2=y^2=z^2=xyz=-1\).
The target quantity \(F(N)\) is the number of ordered pairs of blocks \((A,B)\) whose quaternion values multiply to the identity, equivalently \(B=A^{-1}\) inside \(Q_8\). For \(N=10^6\), a naive \(O(N^2)\) comparison over block pairs is out of the question. The entire solution works because each 50-letter block collapses to one of only eight quaternion states, and those states can be recognized from a tiny parity signature.
The decisive observation is that a word in the quaternion generators is determined by two mod-2 pieces of information: the parity of the number of \(x\), \(y\), and \(z\) letters, and the parity of the swaps needed to sort the word into canonical order \(x \lt y \lt z\).
Take one 50-letter block \(W\). Let \(n_x,n_y,n_z\) be its letter counts, and let
$$p_x\equiv n_x \pmod 2,\qquad p_y\equiv n_y \pmod 2,\qquad p_z\equiv n_z \pmod 2.$$
Also define \(I(W)\) to be the inversion count of the word modulo \(2\) with respect to the alphabet order \(x \lt y \lt z\). In other words, \(I(W)\) records whether an odd or even number of adjacent swaps is needed to sort the letters.
In the quaternion group the generators anticommute in pairs:
$$yx=-xy,\qquad zx=-xz,\qquad zy=-yz.$$
Therefore every swap of two out-of-order letters contributes a factor of \(-1\). After sorting the word, we obtain
$$W = (-1)^{I(W)} x^{n_x} y^{n_y} z^{n_z}.$$
This is why inversion parity is exactly the right sign invariant.
Because \(x^2=y^2=z^2=-1\), each exponent can be stripped down to its parity:
$$x^{n_x} y^{n_y} z^{n_z}=(-1)^{\lfloor n_x/2\rfloor+\lfloor n_y/2\rfloor+\lfloor n_z/2\rfloor}x^{p_x}y^{p_y}z^{p_z}.$$
The block length is fixed at \(50\), so \(n_x+n_y+n_z=50\) is even. Hence \(p_x+p_y+p_z\) must also be even, which means only four parity vectors can occur:
$$ (0,0,0),\ (0,1,1),\ (1,0,1),\ (1,1,0). $$
If we encode the parity vector as
$$m=4p_x+2p_y+p_z,$$
then the only reachable masks are \(m\in\{0,3,5,6\}\), although the implementations keep an \(8\times 2\) table for convenience.
Using \(n_x+n_y+n_z=50\), the square contribution can also be written as
$$\lfloor n_x/2\rfloor+\lfloor n_y/2\rfloor+\lfloor n_z/2\rfloor=\frac{50-(p_x+p_y+p_z)}{2}.$$
So the quaternion value of the whole block is completely determined by the pair \((m,I(W))\).
The parity mask tells us which coset of the center \(\{\pm1\}\) the block lands in. If \(m=0\), the block evaluates to either \(1\) or \(-1\). If \(m\in\{3,5,6\}\), it evaluates to one of the three order-4 pairs \(\{\pm x\}\), \(\{\pm y\}\), or \(\{\pm z\}\). Distinct masks cannot be inverses of one another, so inverse pairs must come from the same mask.
Now compare the two cases:
When \(m=0\), the value is central, so \(q^{-1}=q\). Two blocks with mask \(0\) are inverse exactly when their sign bits agree, which means their inversion parities agree as well.
When \(m\neq 0\), the value has order \(4\), so \(q^{-1}=-q\). Inside a fixed nonzero mask, taking the inverse flips the sign but stays on the same quaternion axis. Therefore two blocks with the same nonzero mask are inverse exactly when their inversion parities are opposite.
Let \(c_{m,0}\) and \(c_{m,1}\) be the numbers of blocks with mask \(m\) and inversion parity \(0\) or \(1\). Since ordered pairs are counted, one mask contributes
$$\Phi(m,c_{m,0},c_{m,1})= \begin{cases} c_{m,0}^2+c_{m,1}^2,& m=0,\\ 2c_{m,0}c_{m,1},& m\neq 0. \end{cases}$$
Summing over all masks gives
$$F(N)=\sum_{m=0}^{7}\Phi(m,c_{m,0},c_{m,1}).$$
Only the four even-parity masks can appear, so the remaining table entries stay zero automatically.
A full block has length \(50\), but a shorter even-length example shows the same algebra. Consider
$$A=zxyx,\qquad B=zyxx.$$
Both words have count parities \((p_x,p_y,p_z)=(0,1,1)\), so they lie in the same nonzero mask. For \(A\), the inversion count is \(4\), hence
$$A = (+1)\,x^2yz = -yz = -x.$$
For \(B\), the inversion count is \(5\), hence
$$B = (-1)\,x^2yz = +x.$$
The parity mask is the same, but the inversion parity flips, so the two words become opposite signs on the same quaternion axis. Consequently
$$AB=(-x)(x)=1.$$
This is exactly the rule used by the algorithm: same nonzero mask, opposite inversion parity.
The C++, Python, and Java implementations never materialize the full \(50N\)-letter stream. They keep the current congruential state \(a\), produce the next residue \(a\bmod 3\), and consume the stream block by block. Within one block they maintain the three count parities \((p_x,p_y,p_z)\) and the inversion parity \(I\).
The update rules come directly from the definition of inversions. Appending an \(x\) creates inversions with every earlier \(y\) and \(z\), so the inversion parity toggles by \(p_y\oplus p_z\). Appending a \(y\) creates inversions with earlier \(z\), so it toggles by \(p_z\). Appending a \(z\) creates no new inversion. After processing the letter, the corresponding count parity bit is toggled.
After 50 letters, the block is represented by its mask \(m=4p_x+2p_y+p_z\) and its inversion parity. The implementation increments one counter in a fixed-size table indexed by those two values. Once all \(N\) blocks have been classified, the final answer is the closed-form aggregation above: for mask \(0\) it adds squares, and for every nonzero reachable mask it adds twice the cross product of the two inversion-parity counts.
Before producing the final result for \(N=10^6\), the implementations also verify the published checkpoints \(F(10)=13\) and \(F(100)=1224\). That confirmation is useful because the whole method depends on getting the sign convention exactly right.
Each block requires exactly 50 generator steps and 50 constant-time state updates, so the total running time is \(O(N)\). There is no quadratic pair scan: the pair counting is reduced to a constant-size summary over at most eight masks and two inversion classes.
Memory usage is \(O(1)\). Apart from the current generator value and a few parity bits, the algorithm stores only the \(8\times 2\) count table. This is the essential gain: millions of blocks are compressed into a handful of counters, and the expensive group comparisons disappear entirely.
Aus der Kongruenzfolge
$$a_{n+1}\equiv 8888a_n \pmod{888888883},\qquad a_0=88888888,$$
wird durch \(b_n=a_n\bmod 3\) eine Buchstabenfolge erzeugt, wobei \(0,1,2\) den Symbolen \(x,y,z\) entsprechen. Die ersten \(50N\) Symbole werden in \(N\) aufeinanderfolgende Blöcke der Länge \(50\) zerlegt. Jeder Block wird dann als Wort in der Quaternionengruppe \(Q_8=\{\pm1,\pm x,\pm y,\pm z\}\) mit den Relationen \(x^2=y^2=z^2=xyz=-1\) gelesen.
Gesucht ist \(F(N)\), also die Anzahl geordneter Blockpaare \((A,B)\), deren Quaternionenwerte zum neutralen Element multiplizieren; äquivalent dazu ist \(B=A^{-1}\). Ein naiver Vergleich aller Blockpaare wäre für \(N=10^6\) unbrauchbar. Die Lösung funktioniert, weil jeder 50er-Block auf eine winzige Zustandsbeschreibung reduziert werden kann.
Entscheidend ist, dass ein Wort in den Generatoren \(x,y,z\) durch zwei Paritätsinvarianten beschrieben werden kann: durch die Parität der Buchstabenanzahlen und durch die Parität der Vertauschungen, die nötig sind, um das Wort in die kanonische Reihenfolge \(x \lt y \lt z\) zu bringen.
Betrachte einen einzelnen Block \(W\) der Länge 50. Sei \(n_x,n_y,n_z\) die Anzahl der drei Buchstaben und
$$p_x\equiv n_x \pmod 2,\qquad p_y\equiv n_y \pmod 2,\qquad p_z\equiv n_z \pmod 2.$$
Außerdem sei \(I(W)\) die Inversionszahl des Wortes modulo \(2\) bezüglich der Ordnung \(x \lt y \lt z\). Sie sagt also, ob eine gerade oder ungerade Anzahl benachbarter Vertauschungen zum Sortieren nötig ist.
In \(Q_8\) antikommutieren die Generatoren paarweise:
$$yx=-xy,\qquad zx=-xz,\qquad zy=-yz.$$
Jede Vertauschung zweier falsch geordneter Nachbarn liefert daher einen Faktor \(-1\). Nach dem Sortieren gilt
$$W = (-1)^{I(W)} x^{n_x} y^{n_y} z^{n_z}.$$
Genau deshalb ist die Inversionsparität das richtige Vorzeicheninvariant.
Wegen \(x^2=y^2=z^2=-1\) kann jeder Exponent auf seine Parität reduziert werden:
$$x^{n_x} y^{n_y} z^{n_z}=(-1)^{\lfloor n_x/2\rfloor+\lfloor n_y/2\rfloor+\lfloor n_z/2\rfloor}x^{p_x}y^{p_y}z^{p_z}.$$
Da der Block immer Länge 50 hat, ist \(n_x+n_y+n_z=50\) gerade. Also muss auch \(p_x+p_y+p_z\) gerade sein. Es bleiben genau vier mögliche Paritätsvektoren:
$$ (0,0,0),\ (0,1,1),\ (1,0,1),\ (1,1,0). $$
Kodiert man den Vektor als
$$m=4p_x+2p_y+p_z,$$
dann sind nur \(m\in\{0,3,5,6\}\) erreichbar, auch wenn die Implementierungen aus Einfachheitsgründen eine vollständige \(8\times 2\)-Tabelle verwenden.
Mit \(n_x+n_y+n_z=50\) kann der Beitrag der Quadrate auch als
$$\lfloor n_x/2\rfloor+\lfloor n_y/2\rfloor+\lfloor n_z/2\rfloor=\frac{50-(p_x+p_y+p_z)}{2}$$
geschrieben werden. Damit ist der Quaternionenwert des ganzen Blocks vollständig durch \((m,I(W))\) bestimmt.
Die Paritätsmaske legt fest, in welcher Nebenklasse des Zentrums \(\{\pm1\}\) der Block liegt. Für \(m=0\) ist der Wert entweder \(1\) oder \(-1\). Für \(m\in\{3,5,6\}\) liegt der Wert in einem der drei Paare \(\{\pm x\}\), \(\{\pm y\}\) oder \(\{\pm z\}\). Verschiedene Masken können daher nicht invers zueinander sein; inverse Paare müssen dieselbe Maske besitzen.
Nun gibt es zwei Fälle. Ist \(m=0\), dann ist \(q^{-1}=q\), denn \(\pm1\) sind selbstinvers. Zwei Blöcke mit Maske 0 sind also genau dann invers, wenn ihre Vorzeichen übereinstimmen, also wenn ihre Inversionsparitäten übereinstimmen.
Ist \(m\neq 0\), dann hat das Element Ordnung 4 und erfüllt \(q^{-1}=-q\). Innerhalb einer festen nichtnulligen Maske bleibt die Quaternionenachse gleich, beim Invertieren wechselt nur das Vorzeichen. Deshalb sind zwei Blöcke mit gleicher nichtnulliger Maske genau dann invers, wenn ihre Inversionsparitäten verschieden sind.
Bezeichne mit \(c_{m,0}\) und \(c_{m,1}\) die Anzahl der Blöcke mit Maske \(m\) und Inversionsparität 0 bzw. 1. Weil geordnete Paare gezählt werden, liefert eine Maske den Beitrag
$$\Phi(m,c_{m,0},c_{m,1})= \begin{cases} c_{m,0}^2+c_{m,1}^2,& m=0,\\ 2c_{m,0}c_{m,1},& m\neq 0. \end{cases}$$
Somit erhält man
$$F(N)=\sum_{m=0}^{7}\Phi(m,c_{m,0},c_{m,1}).$$
Ein echter Block hat Länge 50, aber ein kürzeres Beispiel mit gerader Länge zeigt dieselbe Struktur. Betrachte
$$A=zxyx,\qquad B=zyxx.$$
Beide Wörter haben die Paritäten \((p_x,p_y,p_z)=(0,1,1)\) und liegen damit in derselben nichtnulligen Maske. Für \(A\) ist die Inversionszahl \(4\), also
$$A = (+1)\,x^2yz = -yz = -x.$$
Für \(B\) ist die Inversionszahl \(5\), also
$$B = (-1)\,x^2yz = +x.$$
Gleiche Maske, entgegengesetzte Inversionsparität, also entgegengesetztes Vorzeichen auf derselben Achse. Daher
$$AB=(-x)(x)=1.$$
Genau diese Regel verwendet der Algorithmus für die nichtnulligen Masken.
Die C++-, Python- und Java-Implementierungen speichern niemals den gesamten Strom aus \(50N\) Symbolen. Stattdessen halten sie nur den aktuellen Zustand \(a\) des Kongruenzgenerators, bilden \(a\bmod 3\) und verbrauchen die Folge Block für Block. Innerhalb eines Blocks werden nur die drei Zählparitäten \((p_x,p_y,p_z)\) und die Inversionsparität \(I\) fortgeschrieben.
Die Aktualisierung folgt direkt aus der Definition der Inversionen. Ein angehängtes \(x\) erzeugt Inversionen mit allen bisherigen \(y\) und \(z\), also wird \(I\) um \(p_y\oplus p_z\) umgeschaltet. Ein angehängtes \(y\) erzeugt Inversionen mit bisherigen \(z\), also wird um \(p_z\) umgeschaltet. Ein \(z\) erzeugt keine neue Inversion. Danach wird jeweils das passende Paritätsbit des Buchstabenzählers invertiert.
Nach 50 Zeichen ist der Block vollständig durch die Maske \(m=4p_x+2p_y+p_z\) und die Inversionsparität beschrieben. Die Implementierung erhöht dann genau einen Eintrag in einer kleinen Tabelle. Sind alle \(N\) Blöcke klassifiziert, wird die geschlossene Formel ausgewertet: für Maske 0 werden Quadrate addiert, für jede erreichbare nichtnullige Maske das Doppelte des Kreuzprodukts der beiden Inversionsklassen.
Vor der Ausgabe für \(N=10^6\) werden außerdem die bekannten Kontrollwerte \(F(10)=13\) und \(F(100)=1224\) überprüft. Das ist sinnvoll, weil die Methode sehr kompakt ist und bereits ein einziges falsches Vorzeichen das Ergebnis verfälschen würde.
Jeder Block benötigt genau 50 Generatorschritte und 50 Zustandsupdates konstanter Kosten. Insgesamt ist die Laufzeit daher \(O(N)\). Eine quadratische Paarprüfung findet nicht statt; die Paarzählung ist auf eine Auswertung über konstant viele Tabellenfelder reduziert.
Der Speicherbedarf ist \(O(1)\). Neben dem aktuellen Generatorwert und einigen Paritätsbits wird nur eine \(8\times 2\)-Tabelle gespeichert. Der wesentliche Gewinn besteht also darin, Millionen von Blöcken auf wenige Zähler zusammenzudrücken.
Önce
$$a_{n+1}\equiv 8888a_n \pmod{888888883},\qquad a_0=88888888,$$
dizisi üretiliyor ve her adımda \(b_n=a_n\bmod 3\) alınarak \(0,1,2\) kalıntıları sırasıyla \(x,y,z\) harflerine çevriliyor. İlk \(50N\) harf, uzunluğu 50 olan ardışık \(N\) bloğa ayrılıyor. Her blok da \(x^2=y^2=z^2=xyz=-1\) bağıntılarına sahip kuaterniyon grubu \(Q_8=\{\pm1,\pm x,\pm y,\pm z\}\) içinde bir kelime olarak değerlendiriliyor.
İstenen \(F(N)\), kuaterniyon değerleri çarpıldığında birim elemanı veren sıralı blok çiftlerinin \((A,B)\) sayısıdır; eşdeğer olarak \(B=A^{-1}\). \(N=10^6\) için bütün blok çiftlerini tek tek karşılaştırmak imkansızdır. Çözüm, her 50 harfli bloğun aslında çok küçük bir parite durumuna indirgenebilmesine dayanır.
Temel fikir şu: bir bloktaki tam harf sayıları değil, yalnızca üç harfin sayı pariteleri ve kelimeyi \(x \lt y \lt z\) düzenine sokmak için gereken takasların paritesi önemlidir. Bu iki bilgi, bloktan çıkan kuaterniyonu belirlemeye yeter.
Tek bir blok \(W\) alalım. İçindeki \(x,y,z\) sayıları \(n_x,n_y,n_z\) olsun ve
$$p_x\equiv n_x \pmod 2,\qquad p_y\equiv n_y \pmod 2,\qquad p_z\equiv n_z \pmod 2.$$
Ayrıca \(I(W)\), \(x \lt y \lt z\) alfabesine göre terslik sayısının mod 2 değerini göstersin. Yani \(I(W)\), kelimeyi sıralamak için gereken komşu takas sayısının tek mi çift mi olduğunu kaydeder.
Kuaterniyon grubunda üreteçler ikişerli antikomütatiftir:
$$yx=-xy,\qquad zx=-xz,\qquad zy=-yz.$$
Bu yüzden sırası bozuk iki harfi yer değiştirmenin bedeli bir adet \(-1\) çarpanıdır. Bütün harfler sıralandığında
$$W = (-1)^{I(W)} x^{n_x} y^{n_y} z^{n_z}$$
elde edilir. Demek ki terslik paritesi, kelimenin işaretini taşıyan doğru özettir.
\(x^2=y^2=z^2=-1\) olduğu için her üs sadece kendi paritesine kadar indirgenebilir:
$$x^{n_x} y^{n_y} z^{n_z}=(-1)^{\lfloor n_x/2\rfloor+\lfloor n_y/2\rfloor+\lfloor n_z/2\rfloor}x^{p_x}y^{p_y}z^{p_z}.$$
Blok uzunluğu sabit olarak 50 olduğu için \(n_x+n_y+n_z=50\) çifttir. O halde \(p_x+p_y+p_z\) de çift olmak zorundadır. Bu da yalnızca dört parite vektörü bırakır:
$$ (0,0,0),\ (0,1,1),\ (1,0,1),\ (1,1,0). $$
Parite vektörünü
$$m=4p_x+2p_y+p_z$$
şeklinde kodlarsak, yalnızca \(m\in\{0,3,5,6\}\) değerleri gerçekten oluşabilir. Uygulamalar sadelik için \(8\times 2\) boyutlu tam tablo tutar; erişilemeyen hücreler zaten sıfır kalır.
Üstelik 50 sabit olduğu için karelerden gelen işaret
$$\lfloor n_x/2\rfloor+\lfloor n_y/2\rfloor+\lfloor n_z/2\rfloor=\frac{50-(p_x+p_y+p_z)}{2}$$
olur. Böylece tüm blok değeri yalnızca \((m,I(W))\) çiftiyle belirlenir.
Maske, bloğun merkezin \(\{\pm1\}\) hangi yan sınıfına düştüğünü belirler. \(m=0\) ise blok değeri ya \(1\) ya da \(-1\) olur. \(m\in\{3,5,6\}\) ise değer, \(\{\pm x\}\), \(\{\pm y\}\) ya da \(\{\pm z\}\) çiftlerinden birine düşer. Farklı maskeler birbirinin tersi olamaz; ters çiftler aynı maskeden gelmek zorundadır.
Buradan iki durum çıkar. \(m=0\) için eleman merkezdedir ve \(q^{-1}=q\) olur. Dolayısıyla maske 0 içindeki iki blok ancak işaretleri aynıysa, yani terslik pariteleri aynıysa birbirinin tersidir.
\(m\neq 0\) için elemanın mertebesi 4'tür ve \(q^{-1}=-q\) olur. Sabit bir sıfır olmayan maske içinde eksen değişmez, yalnızca işaret döner. Bu nedenle aynı sıfır olmayan maske içindeki iki blok, ancak terslik pariteleri zıt ise birbirinin tersidir.
Maske \(m\) ve terslik paritesi \(0\) veya \(1\) olan blok sayılarını \(c_{m,0}\) ve \(c_{m,1}\) ile gösterelim. Sıralı çift sayıldığı için tek maskenin katkısı
$$\Phi(m,c_{m,0},c_{m,1})= \begin{cases} c_{m,0}^2+c_{m,1}^2,& m=0,\\ 2c_{m,0}c_{m,1},& m\neq 0 \end{cases}$$
olur. Sonuç olarak
$$F(N)=\sum_{m=0}^{7}\Phi(m,c_{m,0},c_{m,1})$$
formülüne ulaşılır.
Gerçek problemde blok uzunluğu 50'dir; yine de daha kısa bir çift uzunluklu örnek aynı mantığı açıkça gösterir. Şu iki kelimeyi ele alalım:
$$A=zxyx,\qquad B=zyxx.$$
İkisi de \((p_x,p_y,p_z)=(0,1,1)\) paritesine sahiptir; yani aynı sıfır olmayan maskeye düşer. \(A\) için terslik sayısı \(4\) olduğundan
$$A = (+1)\,x^2yz = -yz = -x.$$
\(B\) için terslik sayısı \(5\) olduğundan
$$B = (-1)\,x^2yz = +x.$$
Aynı maske, zıt terslik paritesi ve aynı eksen üzerindeki zıt işaretler: dolayısıyla
$$AB=(-x)(x)=1.$$
Algoritmanın saydığı tam durum budur.
C++, Python ve Java uygulamaları bütün \(50N\) harfini belleğe almaz. Bunun yerine mevcut kongrüans durumu \(a\) tutulur, \(a\bmod 3\) ile bir sonraki harf elde edilir ve akış blok blok tüketilir. Tek bir blok içinde yalnızca \((p_x,p_y,p_z)\) parite bitleri ile terslik paritesi \(I\) güncellenir.
Güncelleme kuralları doğrudan terslik tanımından gelir. Sona eklenen bir \(x\), kendisinden önce gelen tüm \(y\) ve \(z\) harfleriyle yeni terslik oluşturur; bu yüzden \(I\), \(p_y\oplus p_z\) kadar çevrilir. Eklenen bir \(y\), önceki \(z\)'lerle terslik oluşturur; yani \(I\), \(p_z\) kadar çevrilir. \(z\) harfi yeni terslik üretmez. Sonra ilgili harfin sayaç paritesi bir kez çevrilir.
50 harf tamamlanınca blok, maske \(m=4p_x+2p_y+p_z\) ve terslik paritesi ile temsil edilir. Uygulama bu iki değere karşılık gelen tek sayaç hücresini artırır. Bütün bloklar sınıflandırıldıktan sonra son cevap kapalı formülle hesaplanır: maske 0 için kareler, her sıfır olmayan erişilebilir maske için ise iki terslik sınıfının çarpımının iki katı toplanır.
Son büyük hesap yapılmadan önce, yayımlanmış kontrol değerleri olan \(F(10)=13\) ve \(F(100)=1224\) da doğrulanır. Yöntemin omurgası işaret pariteleri olduğu için bu tür bir kontrol özellikle değerlidir.
Her blok tam 50 üreteç adımı ve 50 sabit-zamanlı durum güncellemesi gerektirir. Bu yüzden toplam süre \(O(N)\)'dir. Blok çiftleri üzerinde ayrıca karesel bir dolaşım yoktur; son toplama sabit boyutlu tablo üzerinden yapılır.
Bellek kullanımı \(O(1)\)'dir. Mevcut üreteç değeri, birkaç parite biti ve \(8\times 2\) sayaç tablosu dışında ek depolama gerekmez. Esas kazanç, milyonlarca bloğun bir avuç sayaçta özetlenmesidir.
Se parte de la sucesion congruencial
$$a_{n+1}\equiv 8888a_n \pmod{888888883},\qquad a_0=88888888,$$
y se toma \(b_n=a_n\bmod 3\). Los residuos \(0,1,2\) se interpretan como las letras \(x,y,z\). Los primeros \(50N\) simbolos se agrupan en \(N\) bloques consecutivos de longitud \(50\), y cada bloque se evalua como una palabra del grupo cuaternionico \(Q_8=\{\pm1,\pm x,\pm y,\pm z\}\) con relaciones \(x^2=y^2=z^2=xyz=-1\).
La cantidad buscada \(F(N)\) es el numero de pares ordenados de bloques \((A,B)\) tales que sus valores en \(Q_8\) multiplican al elemento identidad, es decir, \(B=A^{-1}\). Para \(N=10^6\), comparar todos los pares de bloques seria inviable. La solucion funciona porque cada bloque de 50 letras se comprime en un estado muy pequeno descrito solo por paridades.
La idea central es que una palabra en los generadores \(x,y,z\) queda determinada, para este problema, por dos datos modulo \(2\): la paridad de cuantas veces aparece cada letra y la paridad del numero de inversiones necesarias para ordenar la palabra en el orden canonico \(x \lt y \lt z\).
Tomemos un bloque \(W\). Sean \(n_x,n_y,n_z\) los numeros de letras \(x,y,z\), y definamos
$$p_x\equiv n_x \pmod 2,\qquad p_y\equiv n_y \pmod 2,\qquad p_z\equiv n_z \pmod 2.$$
Sea tambien \(I(W)\) la paridad del numero de inversiones de la palabra respecto al alfabeto \(x \lt y \lt z\). Es decir, \(I(W)\) indica si hacen falta un numero par o impar de intercambios adyacentes para ordenar el bloque.
En el grupo cuaternionico los generadores anticonmutan por pares:
$$yx=-xy,\qquad zx=-xz,\qquad zy=-yz.$$
Cada intercambio de dos letras desordenadas introduce por tanto un factor \(-1\). Al ordenar la palabra obtenemos
$$W = (-1)^{I(W)} x^{n_x} y^{n_y} z^{n_z}.$$
Por eso la paridad de inversiones es exactamente el bit de signo correcto.
Como \(x^2=y^2=z^2=-1\), cada exponente se reduce a su paridad:
$$x^{n_x} y^{n_y} z^{n_z}=(-1)^{\lfloor n_x/2\rfloor+\lfloor n_y/2\rfloor+\lfloor n_z/2\rfloor}x^{p_x}y^{p_y}z^{p_z}.$$
La longitud del bloque es siempre \(50\), luego \(n_x+n_y+n_z=50\) es par. En consecuencia \(p_x+p_y+p_z\) tambien es par, de modo que solo pueden aparecer cuatro vectores:
$$ (0,0,0),\ (0,1,1),\ (1,0,1),\ (1,1,0). $$
Si codificamos la paridad como
$$m=4p_x+2p_y+p_z,$$
los unicos valores alcanzables son \(m\in\{0,3,5,6\}\), aunque la implementacion reserva una tabla completa de tamano \(8\times 2\).
Ademas, como la longitud es fija, el aporte de los cuadrados tambien se puede escribir como
$$\lfloor n_x/2\rfloor+\lfloor n_y/2\rfloor+\lfloor n_z/2\rfloor=\frac{50-(p_x+p_y+p_z)}{2}.$$
Asi, el valor cuaternionico del bloque completo queda determinado por \((m,I(W))\).
La mascara de paridad indica en que clase lateral del centro \(\{\pm1\}\) cae el bloque. Si \(m=0\), el valor es \(1\) o \(-1\). Si \(m\in\{3,5,6\}\), el valor pertenece a uno de los tres pares \(\{\pm x\}\), \(\{\pm y\}\) o \(\{\pm z\}\). Dos mascaras distintas no pueden dar elementos inversos; por eso los pares inversos deben compartir la misma mascara.
Hay entonces dos casos. Para \(m=0\), el elemento es central y satisface \(q^{-1}=q\). Dos bloques con mascara 0 son inversos exactamente cuando sus signos coinciden, es decir, cuando coinciden sus paridades de inversion.
Para \(m\neq 0\), el elemento tiene orden 4 y cumple \(q^{-1}=-q\). Dentro de una mascara no nula fija, tomar el inverso conserva el mismo eje cuaternionico y solo cambia el signo. Por ello dos bloques con la misma mascara no nula son inversos exactamente cuando sus paridades de inversion son opuestas.
Si \(c_{m,0}\) y \(c_{m,1}\) cuentan los bloques con mascara \(m\) y paridad de inversion 0 o 1, la contribucion de una mascara, al contar pares ordenados, es
$$\Phi(m,c_{m,0},c_{m,1})= \begin{cases} c_{m,0}^2+c_{m,1}^2,& m=0,\\ 2c_{m,0}c_{m,1},& m\neq 0. \end{cases}$$
Por tanto
$$F(N)=\sum_{m=0}^{7}\Phi(m,c_{m,0},c_{m,1}).$$
El problema real usa longitud 50, pero un ejemplo mas corto y de longitud par muestra la misma estructura. Consideremos
$$A=zxyx,\qquad B=zyxx.$$
Ambas palabras tienen paridades \((p_x,p_y,p_z)=(0,1,1)\), asi que caen en la misma mascara no nula. Para \(A\), el numero de inversiones es \(4\), luego
$$A = (+1)\,x^2yz = -yz = -x.$$
Para \(B\), el numero de inversiones es \(5\), luego
$$B = (-1)\,x^2yz = +x.$$
La mascara es la misma, la paridad de inversiones cambia y el signo se invierte sobre el mismo eje. Entonces
$$AB=(-x)(x)=1.$$
Esa es exactamente la regla que explota el algoritmo.
Las implementaciones en C++, Python y Java no construyen la cadena completa de \(50N\) letras. Conservan solo el estado actual \(a\) del generador congruencial, producen el siguiente residuo \(a\bmod 3\) y consumen la secuencia bloque por bloque. Dentro de cada bloque se mantienen unicamente las tres paridades de conteo \((p_x,p_y,p_z)\) y la paridad de inversiones \(I\).
Las reglas de actualizacion salen directamente de la definicion de inversion. Anadir una \(x\) al final crea inversiones con todas las \(y\) y \(z\) anteriores, asi que \(I\) cambia por \(p_y\oplus p_z\). Anadir una \(y\) crea inversiones con las \(z\) anteriores, de modo que \(I\) cambia por \(p_z\). Anadir una \(z\) no crea ninguna inversion nueva. Luego se conmuta el bit de paridad de la letra correspondiente.
Tras 50 letras, el bloque queda resumido por la mascara \(m=4p_x+2p_y+p_z\) y la paridad de inversiones. La implementacion incrementa una celda de una tabla fija. Cuando ya se han clasificado los \(N\) bloques, la respuesta se obtiene con la formula cerrada: para la mascara 0 suma cuadrados; para cada mascara alcanzable no nula suma dos veces el producto cruzado de las dos clases de inversion.
Antes de calcular el caso grande \(N=10^6\), las implementaciones comprueban tambien los valores de referencia publicados \(F(10)=13\) y \(F(100)=1224\). Eso da confianza en que los signos y las reglas de inversion se han traducido correctamente.
Cada bloque cuesta exactamente 50 pasos del generador y 50 actualizaciones de estado de tiempo constante, de modo que el tiempo total es \(O(N)\). No hay un barrido cuadratico sobre pares de bloques; la comparacion por pares ya esta incorporada en la pequena tabla de conteos.
La memoria es \(O(1)\). Aparte del estado actual del generador y unos pocos bits de paridad, solo se guarda una tabla \(8\times 2\). El ahorro esencial consiste en comprimir millones de bloques en un punado de contadores.
先定义同余递推
$$a_{n+1}\equiv 8888a_n \pmod{888888883},\qquad a_0=88888888,$$
再取 \(b_n=a_n\bmod 3\)。余数 \(0,1,2\) 分别映射成字母 \(x,y,z\)。前 \(50N\) 个字母被切成 \(N\) 个连续的 50 字母块，每个块都被看成四元数群 \(Q_8=\{\pm1,\pm x,\pm y,\pm z\}\) 中的一个词，其中满足 \(x^2=y^2=z^2=xyz=-1\)。
题目要求的 \(F(N)\) 是满足 \(A\cdot B=1\) 的有序块对 \((A,B)\) 的个数，也就是第二个块的群元素正好是第一个块的逆元。若直接对所有块对逐一比较，复杂度会是 \(O(N^2)\)，对 \(N=10^6\) 完全不可行。真正的突破点在于：一个长度为 50 的块最终只需要一个很小的奇偶状态就能刻画。
这个解法的核心并不是记录完整单词，而是只记录两个模 2 不变量：三种字母出现次数的奇偶性，以及把这个词整理到规范顺序 \(x \lt y \lt z\) 所需交换次数的奇偶性。对四元数群而言，这两部分信息已经足够决定整个块的值。
考虑一个块 \(W\)。设其中 \(x,y,z\) 的出现次数分别为 \(n_x,n_y,n_z\)，并记
$$p_x\equiv n_x \pmod 2,\qquad p_y\equiv n_y \pmod 2,\qquad p_z\equiv n_z \pmod 2.$$
再令 \(I(W)\) 表示相对于字母序 \(x \lt y \lt z\) 的逆序数模 2。也就是说，\(I(W)\) 只关心把这个词排序所需相邻交换次数是奇数还是偶数。
在四元数群里，三个生成元两两反交换：
$$yx=-xy,\qquad zx=-xz,\qquad zy=-yz.$$
因此，每交换一对次序错误的相邻字母，整体就多出一个 \(-1\) 因子。把整个词整理到规范顺序以后，就得到
$$W = (-1)^{I(W)} x^{n_x} y^{n_y} z^{n_z}.$$
这正说明了为什么“逆序奇偶”恰好就是这个问题里需要保留的符号信息。
因为 \(x^2=y^2=z^2=-1\)，所以每个指数最终只需要保留奇偶性：
$$x^{n_x} y^{n_y} z^{n_z}=(-1)^{\lfloor n_x/2\rfloor+\lfloor n_y/2\rfloor+\lfloor n_z/2\rfloor}x^{p_x}y^{p_y}z^{p_z}.$$
块长固定为 50，所以 \(n_x+n_y+n_z=50\) 是偶数，于是 \(p_x+p_y+p_z\) 也必须是偶数。这立刻把所有可能的奇偶向量压缩成四种：
$$ (0,0,0),\ (0,1,1),\ (1,0,1),\ (1,1,0). $$
如果把三位奇偶向量编码成
$$m=4p_x+2p_y+p_z,$$
那么真正可能出现的只有 \(m\in\{0,3,5,6\}\)。程序为了实现简单仍然保留了完整的 \(8\times 2\) 计数表，但其余掩码自然一直为零。
由于总长度固定，上式中的平方项符号还可以进一步写成
$$\lfloor n_x/2\rfloor+\lfloor n_y/2\rfloor+\lfloor n_z/2\rfloor=\frac{50-(p_x+p_y+p_z)}{2}.$$
因此，一个 50 字母块在群中的值完全由 \((m,I(W))\) 这对状态决定。
奇偶掩码决定了这个块落在中心 \(\{\pm1\}\) 的哪一个陪集里。若 \(m=0\)，块的值只能是 \(1\) 或 \(-1\)。若 \(m\in\{3,5,6\}\)，块的值则落在 \(\{\pm x\}\)、\(\{\pm y\}\)、\(\{\pm z\}\) 三对元素中的某一对。不同掩码不可能互为逆元，所以逆元配对一定发生在同一个掩码内部。
接下来要分两类讨论。对于 \(m=0\)，元素位于中心，满足 \(q^{-1}=q\)。因此两个掩码为 0 的块只有在符号相同的时候才互为逆元，而在这里“符号相同”恰好等价于逆序奇偶相同。
对于 \(m\neq 0\)，元素的阶为 4，满足 \(q^{-1}=-q\)。也就是说，在固定的非零掩码内部，取逆不会改变所在的四元数轴，只会翻转正负号。所以两个同掩码的块只有在逆序奇偶相反时才互为逆元。
记 \(c_{m,0}\) 和 \(c_{m,1}\) 为掩码 \(m\) 下逆序奇偶分别为 0、1 的块数。由于题目统计的是有序块对，一个掩码的贡献是
$$\Phi(m,c_{m,0},c_{m,1})= \begin{cases} c_{m,0}^2+c_{m,1}^2,& m=0,\\ 2c_{m,0}c_{m,1},& m\neq 0. \end{cases}$$
于是总答案为
$$F(N)=\sum_{m=0}^{7}\Phi(m,c_{m,0},c_{m,1}).$$
真实题目中的块长是 50，不过用一个更短、长度仍为偶数的例子更容易看清规律。考虑
$$A=zxyx,\qquad B=zyxx.$$
这两个词的字母奇偶都是 \((p_x,p_y,p_z)=(0,1,1)\)，因此属于同一个非零掩码。对 \(A\) 来说，逆序数是 4，所以
$$A = (+1)\,x^2yz = -yz = -x.$$
对 \(B\) 来说，逆序数是 5，所以
$$B = (-1)\,x^2yz = +x.$$
可以看到：掩码相同，但逆序奇偶相反，于是落在同一条四元数轴上的相反符号。于是
$$AB=(-x)(x)=1.$$
这正是程序最终利用的判定规则。
C++、Python 和 Java 实现都不会把全部 \(50N\) 个字母先存下来。它们只保留当前的同余生成器状态 \(a\)，每次取出 \(a\bmod 3\) 得到下一个字母，然后按块连续消费这个序列。在一个块内部，只需要维护三位计数奇偶 \((p_x,p_y,p_z)\) 和一位逆序奇偶 \(I\)。
更新规则直接来自逆序定义。若当前读到的是 \(x\)，它会与之前所有的 \(y\) 和 \(z\) 形成新的逆序，因此 \(I\) 要按 \(p_y\oplus p_z\) 翻转。若读到的是 \(y\)，它只会与之前的 \(z\) 形成逆序，因此 \(I\) 按 \(p_z\) 翻转。若读到的是 \(z\)，则不会新增逆序。随后再翻转对应字母的计数奇偶位。
当 50 个字母处理完以后，这个块就只剩下掩码 \(m=4p_x+2p_y+p_z\) 和逆序奇偶两个信息。实现将相应的表项加一。全部 \(N\) 个块分类完成后，就按上面的闭式公式汇总答案：对掩码 0，累加两个平方项；对每个可达的非零掩码，累加两类逆序奇偶计数的两倍乘积。
在真正计算 \(N=10^6\) 之前，实现还会先验证题面给出的检查值 \(F(10)=13\) 和 \(F(100)=1224\)。由于整个方法高度依赖符号约定，这一步能有效排除奇偶处理中的微小错误。
每个块恰好执行 50 次生成器迭代和 50 次常数时间状态更新，因此总时间复杂度是 \(O(N)\)。不存在对所有块对的二次枚举；配对统计已经被压缩到一个常数大小的状态表上。
空间复杂度是 \(O(1)\)。除当前生成器状态、几个奇偶位和一张 \(8\times 2\) 计数表之外，不需要额外存储。真正的效率提升就在于：数百万个块被压缩成了极少数计数器。
Задается рекуррентная последовательность
$$a_{n+1}\equiv 8888a_n \pmod{888888883},\qquad a_0=88888888,$$
после чего берется \(b_n=a_n\bmod 3\). Остатки \(0,1,2\) интерпретируются как буквы \(x,y,z\). Первые \(50N\) символов разбиваются на \(N\) последовательных блоков длины \(50\), и каждый блок рассматривается как слово в кватернионной группе \(Q_8=\{\pm1,\pm x,\pm y,\pm z\}\), где \(x^2=y^2=z^2=xyz=-1\).
Искомая величина \(F(N)\) равна числу упорядоченных пар блоков \((A,B)\), для которых произведение их значений в \(Q_8\) равно единице, то есть \(B=A^{-1}\). Прямой перебор всех пар блоков имеет квадратичную стоимость и для \(N=10^6\) непригоден. Решение становится возможным потому, что каждый блок длины 50 сжимается до очень маленького инвариантного состояния.
Ключевой факт состоит в том, что для данного слова достаточно знать две вещи по модулю 2: четности числа букв \(x,y,z\) и четность числа перестановок, нужных для приведения слова к каноническому порядку \(x \lt y \lt z\). Эти данные уже полностью определяют значение блока в группе.
Рассмотрим один блок \(W\). Пусть \(n_x,n_y,n_z\) — количества букв \(x,y,z\), а
$$p_x\equiv n_x \pmod 2,\qquad p_y\equiv n_y \pmod 2,\qquad p_z\equiv n_z \pmod 2.$$
Пусть также \(I(W)\) — четность числа инверсий слова относительно порядка \(x \lt y \lt z\). Иными словами, это четность числа соседних обменов, необходимых для сортировки букв.
В кватернионной группе образующие попарно антикоммутируют:
$$yx=-xy,\qquad zx=-xz,\qquad zy=-yz.$$
Значит, каждая перестановка двух соседних букв в неправильном порядке вносит множитель \(-1\). После сортировки получаем
$$W = (-1)^{I(W)} x^{n_x} y^{n_y} z^{n_z}.$$
Именно поэтому четность инверсий служит нужным битом знака.
Так как \(x^2=y^2=z^2=-1\), каждый показатель можно сократить до четности:
$$x^{n_x} y^{n_y} z^{n_z}=(-1)^{\lfloor n_x/2\rfloor+\lfloor n_y/2\rfloor+\lfloor n_z/2\rfloor}x^{p_x}y^{p_y}z^{p_z}.$$
Длина блока фиксирована и равна 50, поэтому \(n_x+n_y+n_z=50\) четно. Отсюда следует, что \(p_x+p_y+p_z\) тоже четно, а значит возможны только четыре вектора четностей:
$$ (0,0,0),\ (0,1,1),\ (1,0,1),\ (1,1,0). $$
Если закодировать их числом
$$m=4p_x+2p_y+p_z,$$
то реально достижимы лишь \(m\in\{0,3,5,6\}\). Реализации для простоты держат полную таблицу \(8\times 2\), но остальные строки в ней всегда остаются нулевыми.
Поскольку суммарная длина известна заранее, вклад от квадратов можно переписать как
$$\lfloor n_x/2\rfloor+\lfloor n_y/2\rfloor+\lfloor n_z/2\rfloor=\frac{50-(p_x+p_y+p_z)}{2}.$$
Следовательно, значение блока целиком определяется парой \((m,I(W))\).
Маска четностей определяет, в какой класс по центру \(\{\pm1\}\) попадает блок. Если \(m=0\), значение равно либо \(1\), либо \(-1\). Если \(m\in\{3,5,6\}\), значение лежит в одной из трех пар \(\{\pm x\}\), \(\{\pm y\}\), \(\{\pm z\}\). Разные маски не могут давать взаимно обратные элементы, поэтому обратные пары всегда находятся внутри одной и той же маски.
Дальше нужно разделить два случая. При \(m=0\) элемент центральный и удовлетворяет \(q^{-1}=q\). Значит, два блока с нулевой маской являются обратными тогда и только тогда, когда у них совпадает знак, то есть совпадает четность инверсий.
При \(m\neq 0\) элемент имеет порядок 4 и выполняется \(q^{-1}=-q\). Внутри фиксированной ненулевой маски взятие обратного сохраняет ту же ось \(x\), \(y\) или \(z\), но меняет знак. Поэтому два блока с одинаковой ненулевой маской являются обратными тогда и только тогда, когда их четности инверсий различны.
Обозначим через \(c_{m,0}\) и \(c_{m,1}\) количество блоков с маской \(m\) и четностью инверсий 0 или 1. Так как считаются упорядоченные пары, вклад одной маски равен
$$\Phi(m,c_{m,0},c_{m,1})= \begin{cases} c_{m,0}^2+c_{m,1}^2,& m=0,\\ 2c_{m,0}c_{m,1},& m\neq 0. \end{cases}$$
Итак,
$$F(N)=\sum_{m=0}^{7}\Phi(m,c_{m,0},c_{m,1}).$$
В самой задаче длина блока равна 50, но короткий пример с четной длиной показывает ту же механику. Рассмотрим
$$A=zxyx,\qquad B=zyxx.$$
Оба слова имеют четности \((p_x,p_y,p_z)=(0,1,1)\), то есть попадают в одну и ту же ненулевую маску. Для \(A\) число инверсий равно 4, поэтому
$$A = (+1)\,x^2yz = -yz = -x.$$
Для \(B\) число инверсий равно 5, поэтому
$$B = (-1)\,x^2yz = +x.$$
Маска одинакова, четность инверсий разная, знак на той же оси меняется на противоположный, и потому
$$AB=(-x)(x)=1.$$
Ровно это условие и использует алгоритм.
Реализации на C++, Python и Java не строят всю строку из \(50N\) символов заранее. Они хранят только текущее состояние конгруэнтного генератора \(a\), получают очередной остаток \(a\bmod 3\) и обрабатывают поток по блокам. Внутри одного блока поддерживаются лишь три бита четности \((p_x,p_y,p_z)\) и один бит четности инверсий \(I\).
Правила обновления прямо следуют из определения инверсии. Если добавлена буква \(x\), она образует инверсии со всеми предыдущими \(y\) и \(z\), значит \(I\) переключается на \(p_y\oplus p_z\). Если добавлена \(y\), новые инверсии возникают только с прежними \(z\), и \(I\) переключается на \(p_z\). Буква \(z\) новых инверсий не создает. После этого переключается нужный бит четности счетчика букв.
После обработки 50 символов блок описывается только маской \(m=4p_x+2p_y+p_z\) и четностью инверсий. Реализация увеличивает соответствующую ячейку маленькой таблицы. Когда все \(N\) блоков классифицированы, ответ получается по закрытой формуле: для маски 0 суммируются квадраты, для каждой достижимой ненулевой маски берется удвоенное произведение двух классов инверсий.
Перед вычислением значения для \(N=10^6\) реализации также проверяют опубликованные контрольные значения \(F(10)=13\) и \(F(100)=1224\). Такая проверка полезна, потому что вся конструкция чувствительна к знакам и четностям.
Каждый блок требует ровно 50 шагов генератора и 50 обновлений состояния за константное время, поэтому общая трудоемкость равна \(O(N)\). Квадратичного перебора пар блоков нет: вся информация для парного счета уже сжата в несколько счетчиков.
Память имеет порядок \(O(1)\). Помимо текущего значения генератора и нескольких битов, хранится только таблица \(8\times 2\). Главный выигрыш состоит в том, что миллионы блоков сводятся к нескольким числам.
نبدأ بالمتتالية التوافقية
$$a_{n+1}\equiv 8888a_n \pmod{888888883},\qquad a_0=88888888,$$
ثم نأخذ \(b_n=a_n\bmod 3\). البواقي \(0,1,2\) تُحوَّل إلى الحروف \(x,y,z\). بعد ذلك تُقسَّم أول \(50N\) حرفًا إلى \(N\) كتل متتالية طول كل منها \(50\)، وتُفسَّر كل كتلة على أنها كلمة في زمرة الكواترنيون \(Q_8=\{\pm1,\pm x,\pm y,\pm z\}\) التي تحقق العلاقات \(x^2=y^2=z^2=xyz=-1\).
الكمية المطلوبة \(F(N)\) هي عدد الأزواج المرتبة من الكتل \((A,B)\) التي يكون فيها حاصل ضرب القيمتين مساويًا للعنصر المحايد، أي عندما تكون قيمة \(B\) هي معكوس قيمة \(A\). لو حاولنا فحص جميع أزواج الكتل مباشرة فسنحصل على كلفة تربيعية لا تصلح إطلاقًا عند \(N=10^6\). الفكرة الأساسية في الحل هي أن كل كتلة بطول 50 تنهار في النهاية إلى حالة صغيرة جدًا يحددها عدد قليل من البتات.
جوهر الحل هو أن كلمة مكوَّنة من الحروف \(x,y,z\) لا نحتاج منها إلا إلى معلومتين بترديد 2: فردية عدد مرات ظهور كل حرف، وفردية عدد التبديلات اللازمة لإعادة ترتيب الكلمة إلى الترتيب القياسي \(x \lt y \lt z\). هاتان المعلومتان تكفيان لتحديد عنصر الكواترنيون الناتج عن الكتلة كلها.
لنأخذ كتلة واحدة \(W\). ولتكن أعداد الحروف فيها \(n_x,n_y,n_z\)، ونعرّف
$$p_x\equiv n_x \pmod 2,\qquad p_y\equiv n_y \pmod 2,\qquad p_z\equiv n_z \pmod 2.$$
ولنرمز بـ \(I(W)\) إلى فردية عدد الانقلابات بالنسبة إلى الترتيب \(x \lt y \lt z\). أي إن \(I(W)\) يسجل فقط هل عدد التبديلات المجاورة المطلوبة لفرز الكلمة زوجي أم فردي.
في زمرة الكواترنيون تتضاد المولدات اثنين اثنين:
$$yx=-xy,\qquad zx=-xz,\qquad zy=-yz.$$
لذلك فإن كل تبديل بين حرفين خارج الترتيب يضيف عاملًا مقداره \(-1\). وبعد فرز الحروف نحصل على
$$W = (-1)^{I(W)} x^{n_x} y^{n_y} z^{n_z}.$$
ومن هنا تأتي أهمية فردية الانقلابات: فهي بالضبط البت الذي يحمل إشارة العنصر الناتج.
بما أن \(x^2=y^2=z^2=-1\)، فيمكن اختزال كل أس إلى فرديته فقط:
$$x^{n_x} y^{n_y} z^{n_z}=(-1)^{\lfloor n_x/2\rfloor+\lfloor n_y/2\rfloor+\lfloor n_z/2\rfloor}x^{p_x}y^{p_y}z^{p_z}.$$
وطول الكتلة ثابت ويساوي \(50\)، لذا فإن \(n_x+n_y+n_z=50\) عدد زوجي. وبالتالي لا بد أن يكون \(p_x+p_y+p_z\) زوجيًا أيضًا، فلا تبقى إلا أربع حالات ممكنة لمتجه الفرديات:
$$ (0,0,0),\ (0,1,1),\ (1,0,1),\ (1,1,0). $$
إذا شفّرنا هذا المتجه بالعدد
$$m=4p_x+2p_y+p_z,$$
فإن القيم الممكنة فعلًا هي فقط \(m\in\{0,3,5,6\}\). تحتفظ التطبيقات بجدول كامل حجمه \(8\times 2\) لسهولة التنفيذ، لكن الخانات الأخرى تبقى صفرية تلقائيًا.
ولأن الطول الكلي ثابت، يمكن كذلك كتابة إسهام المربعات على الصورة
$$\lfloor n_x/2\rfloor+\lfloor n_y/2\rfloor+\lfloor n_z/2\rfloor=\frac{50-(p_x+p_y+p_z)}{2}.$$
إذن قيمة الكتلة في الزمرة تتحدد بالكامل من الزوج \((m,I(W))\).
قناع الفرديات يحدد في أي طبقة بالنسبة إلى المركز \(\{\pm1\}\) يقع العنصر. إذا كان \(m=0\) فإن قيمة الكتلة تكون \(1\) أو \(-1\). وإذا كان \(m\in\{3,5,6\}\) فإن القيمة تقع في أحد الأزواج \(\{\pm x\}\) أو \(\{\pm y\}\) أو \(\{\pm z\}\). لهذا لا يمكن لقناعين مختلفين أن يعطيا عنصرين متعاكسين؛ الأزواج المعكوسة لا بد أن تأتي من القناع نفسه.
بعد ذلك نميز حالتين. عندما يكون \(m=0\)، يكون العنصر مركزيًا ويحقق \(q^{-1}=q\). لذلك فإن كتلتين بالقناع صفر تكونان معكوسين لبعضهما بالضبط عندما تتفق إشارتهما، وهذا في هذه الصياغة يعادل تطابق فردية الانقلابات.
أما عندما يكون \(m\neq 0\)، فالعنصر من الرتبة 4 ويحقق \(q^{-1}=-q\). داخل قناع غير صفري ثابت، أخذ المعكوس لا يغير المحور \(x\) أو \(y\) أو \(z\)، بل يبدل الإشارة فقط. ولهذا فإن كتلتين من القناع غير الصفري نفسه تكونان معكوسين لبعضهما تمامًا عندما تختلف فردية الانقلابات بينهما.
إذا رمزنا بعدد الكتل ذات القناع \(m\) وفردية الانقلابات \(0\) أو \(1\) بـ \(c_{m,0}\) و\(c_{m,1}\)، فإن مساهمة قناع واحد، لأن العد هنا عد للأزواج المرتبة، تساوي
$$\Phi(m,c_{m,0},c_{m,1})= \begin{cases} c_{m,0}^2+c_{m,1}^2,& m=0,\\ 2c_{m,0}c_{m,1},& m\neq 0. \end{cases}$$
ومن ثم نحصل على
$$F(N)=\sum_{m=0}^{7}\Phi(m,c_{m,0},c_{m,1}).$$
الكتلة الحقيقية في المسألة طولها 50، لكن مثالًا أقصر بطول زوجي يوضح الفكرة نفسها بوضوح. خذ الكلمتين
$$A=zxyx,\qquad B=zyxx.$$
كلتاهما تملكان متجه الفرديات \((p_x,p_y,p_z)=(0,1,1)\)، أي إنهما تقعان في القناع غير الصفري نفسه. بالنسبة إلى \(A\)، عدد الانقلابات يساوي \(4\)، لذا
$$A = (+1)\,x^2yz = -yz = -x.$$
وبالنسبة إلى \(B\)، عدد الانقلابات يساوي \(5\)، لذا
$$B = (-1)\,x^2yz = +x.$$
القناع نفسه، لكن فردية الانقلابات معكوسة، فنحصل على إشارتين متعاكستين على المحور نفسه. لذلك
$$AB=(-x)(x)=1.$$
هذه هي القاعدة التي يستغلها الحل حرفيًا.
لا تقوم تطبيقات C++ وPython وJava ببناء السلسلة الكاملة ذات الطول \(50N\). بل تحتفظ فقط بالحالة الحالية \(a\) للمولد التوافقي، ثم تستخرج الباقي \(a\bmod 3\) وتستهلك الأحرف على شكل كتل متتالية. داخل كل كتلة لا نحتاج إلا إلى ثلاث بتات لفردية العد \((p_x,p_y,p_z)\) وبت واحد لفردية الانقلابات \(I\).
قواعد التحديث تأتي مباشرة من تعريف الانقلاب. إذا أضيف حرف \(x\) في النهاية فإنه يكوّن انقلابات جديدة مع كل \(y\) و\(z\) سبقاه، لذلك تُقلَب \(I\) بمقدار \(p_y\oplus p_z\). وإذا أضيف حرف \(y\)، فإنه يكوّن انقلابات فقط مع أحرف \(z\) السابقة، لذا تُقلَب \(I\) بمقدار \(p_z\). أما \(z\) فلا يضيف أي انقلاب جديد. بعد ذلك تُقلَب بتة الفردية الخاصة بعدد الحرف الذي تمت قراءته.
بعد إنهاء 50 حرفًا، تُختزل الكتلة إلى القناع \(m=4p_x+2p_y+p_z\) وإلى فردية الانقلابات. ثم تزداد خانة واحدة في جدول صغير ثابت الحجم. وبعد تصنيف جميع الكتل، تُحسب النتيجة النهائية بالصيغة المغلقة السابقة: للقناع صفر نجمع المربعات، ولكل قناع غير صفري قابل للوصول نجمع ضعفي حاصل ضرب عددي فئتي الانقلابات.
وقبل حساب النتيجة النهائية عند \(N=10^6\)، تتحقق التطبيقات أيضًا من القيم المرجعية المنشورة \(F(10)=13\) و\(F(100)=1224\). هذا مهم لأن الطريقة كلها تعتمد على ضبط الإشارات والزوجيات من دون أي هامش للخطأ.
كل كتلة تحتاج بالضبط إلى 50 خطوة من المولد و50 تحديثًا لحالة صغيرة بزمن ثابت، لذلك يكون الزمن الكلي \(O(N)\). ولا يوجد أي فحص تربيعي على جميع أزواج الكتل؛ إذ تم امتصاص العد الزوجي في جدول ثابت الحجم.
استهلاك الذاكرة هو \(O(1)\). فباستثناء الحالة الحالية للمولد، وبضع بتات، وجدول العد \(8\times 2\)، لا نحتاج إلى أي تخزين إضافي. المكسب الحقيقي هنا هو ضغط ملايين الكتل في بضعة عدادات فقط.