On a \(w\times h\) Lights Out board, pressing a cell toggles that cell and its orthogonal neighbors. Over \(\mathbb{F}_2\), pressing twice cancels, so every press pattern is a binary vector and the puzzle becomes a linear map. Let \(F(w,h)\) denote the number of solvable starting boards of size \(w\times h\). The required quantity is
$$S(w,n)=\sum_{k=1}^{n} F(w,f_k)\pmod{10^9+7},$$
where \(f_1=f_2=1\) and \(f_{k+1}=f_k+f_{k-1}\). The key optimization is to avoid the full \(wh\times wh\) game matrix and reduce the problem to \(w\times w\) matrices over \(\mathbb{F}_2\).
The board can be processed row by row. This turns the two-dimensional Lights Out operator into a one-dimensional transfer recurrence.
Write the press vector on row \(i\) as \(x_i\in \mathbb{F}_2^w\), and the target board row as \(b_i\in \mathbb{F}_2^w\). Define the width matrix \(T_w\in \mathbb{F}_2^{w\times w}\) by
$$T_w=\begin{pmatrix} 1 & 1 & 0 & \cdots & 0\\ 1 & 1 & 1 & \ddots & \vdots\\ 0 & 1 & 1 & \ddots & 0\\ \vdots & \ddots & \ddots & \ddots & 1\\ 0 & \cdots & 0 & 1 & 1 \end{pmatrix}.$$
This matrix describes the effect of pressing inside a single row: the chosen cell itself and its left-right neighbors. Vertical interaction comes from the rows above and below, so row \(i\) satisfies
$$x_{i-1}+T_w x_i+x_{i+1}=b_i,$$
with boundary conditions \(x_0=0\) and \(x_{h+1}=0\). If \(L_{w,h}\) denotes the global Lights Out operator, then the number of solvable boards is the size of its image:
$$F(w,h)=|\operatorname{Im}(L_{w,h})|=2^{\operatorname{rank}(L_{w,h})}.$$
To count the image size, it is enough to know the kernel dimension. In the homogeneous case \(b_i=0\), the row relation becomes
$$x_{i+1}=T_w x_i+x_{i-1}.$$
Now define matrix polynomials \(A_n\) by
$$A_0=0,\qquad A_1=I,\qquad A_{n+2}=T_w A_{n+1}+A_n.$$
Starting from an arbitrary first-row press vector \(x_1\), induction gives
$$x_i=A_i x_1\qquad (i\ge 0).$$
The bottom boundary condition becomes
$$A_{h+1}x_1=0.$$
So each kernel press pattern is determined by one vector in \(\ker(A_{h+1})\), and conversely every vector in \(\ker(A_{h+1})\) produces a valid homogeneous press pattern. Therefore
$$\dim\ker(L_{w,h})=\dim\ker(A_{h+1})=w-\operatorname{rank}(A_{h+1}).$$
By rank-nullity on the full \(wh\)-variable move operator,
$$\operatorname{rank}(L_{w,h})=wh-\left(w-\operatorname{rank}(A_{h+1})\right).$$
Hence
$$F(w,h)=2^{wh-w+\operatorname{rank}(A_{h+1})}=2^{wh-\nu_{w,h}},$$
where \(\nu_{w,h}=w-\operatorname{rank}(A_{h+1})\) is the relevant nullity.
Each \(A_n\) is a polynomial in \(T_w\), so all these matrices commute. Introduce the block matrix
$$M=\begin{pmatrix} T_w & I \\ I & 0 \end{pmatrix}.$$
A standard induction shows
$$M^n=\begin{pmatrix} A_{n+1} & A_n \\ A_n & A_{n-1} \end{pmatrix}\qquad (n\ge 1).$$
Multiplying \(M^mM^n=M^{m+n}\) and comparing blocks gives
$$A_{m+n+1}=A_{m+1}A_{n+1}+A_mA_n,$$
$$A_{m+n}=A_{m+1}A_n+A_mA_{n-1}.$$
Because addition and subtraction are the same in \(\mathbb{F}_2\), the recurrence also implies
$$A_{n-1}=T_wA_n+A_{n+1}.$$
Substituting this into the second identity yields the form used by the implementation:
$$A_{m+n}=A_{m+1}A_n+A_mA_{n+1}+T_wA_mA_n.$$
Let \(m=f_{k-1}\) and \(n=f_{k-2}\). Since \(f_k=m+n\), the previous identities let us compute the pair \((A_{f_k},A_{f_k+1})\) directly from the two preceding Fibonacci pairs:
$$A_{f_k}=A_{m+1}A_n+A_mA_{n+1}+T_wA_mA_n,$$
$$A_{f_k+1}=A_{m+1}A_{n+1}+A_mA_n.$$
This is why the implementations store two consecutive Fibonacci-index pairs instead of recomputing the transfer sequence from scratch for every height. The method still performs matrix multiplications, but it skips the huge gaps between consecutive Fibonacci numbers.
Once \(\operatorname{rank}(A_{h+1})\) is known, the contribution for height \(h\) is
$$F(w,h)=2^{wh-\left(w-\operatorname{rank}(A_{h+1})\right)}.$$
The final answer is taken modulo the prime
$$p=10^9+7.$$
Therefore Fermat's little theorem allows the exponent to be reduced modulo
$$p-1=10^9+6,$$
so only \(wh-\nu_{w,h}\bmod (p-1)\) is needed before modular exponentiation.
For width \(1\), the row matrix is simply
$$T_1=[1].$$
The transfer sequence becomes
$$A_0=0,\qquad A_1=1,\qquad A_2=1,\qquad A_3=A_2+A_1=0.$$
So \(A_{h+1}=A_3\) has rank \(0\), hence nullity \(1\). The full board has \(wh=2\) cells, so
$$\operatorname{rank}(L_{1,2})=2-1=1.$$
Therefore
$$F(1,2)=2^1=2.$$
This matches the small checkpoint used by the implementation. Concretely, on a \(1\times 2\) board both buttons have the same effect, so only the all-off and all-on boards are solvable states.
The C++, Python, and Java implementations all follow the same algebraic plan. They build the width matrix once, store every binary matrix row as packed bits, and use XOR as addition in \(\mathbb{F}_2\). General matrix multiplication scans the set bits of one factor and XORs the corresponding rows of the other factor, while the special multiplication by the tridiagonal width matrix is handled by XORing each row with its immediate neighbors.
For the final sum, the implementation keeps two consecutive Fibonacci-index transfer pairs. Each new term is obtained by four general matrix multiplications, one application of the width matrix, and a few matrix XORs. After that, Gaussian elimination over \(\mathbb{F}_2\) gives the rank of the current transfer matrix, the nullity is converted into the exponent \(wh-\nu\), and fast modular exponentiation yields the contribution to the running sum.
For fixed width \(w\), each matrix has \(w\) rows and \(\lceil w/64\rceil\) machine words per row. Matrix addition costs \(O(w^2/64)\) bit-operations. A general multiplication or a packed Gaussian elimination costs about \(O(w^3/64)\) bit-operations. For \(S(w,n)\), each new Fibonacci term performs a constant number of such matrix operations, so the total running time is \(O(nw^3/64)\), and the memory usage is \(O(w^2/64)\).
Auf einem Lights-Out-Brett der Größe \(w\times h\) schaltet ein Druck auf ein Feld dieses Feld und seine orthogonalen Nachbarn um. Über \(\mathbb{F}_2\) hebt sich doppeltes Drücken auf, daher ist jedes Druckmuster ein Binärvektor und das gesamte Rätsel wird zu einer linearen Abbildung. Sei \(F(w,h)\) die Anzahl der lösbaren Startbretter der Größe \(w\times h\). Gesucht ist
$$S(w,n)=\sum_{k=1}^{n} F(w,f_k)\pmod{10^9+7},$$
wobei \(f_1=f_2=1\) und \(f_{k+1}=f_k+f_{k-1}\) gilt. Die entscheidende Optimierung besteht darin, nicht die volle Spielmatrix der Größe \(wh\times wh\) aufzubauen, sondern alles auf \(w\times w\)-Matrizen über \(\mathbb{F}_2\) zurückzuführen.
Das Brett lässt sich zeilenweise behandeln. Dadurch wird der zweidimensionale Lights-Out-Operator in eine eindimensionale Transferrekursion umgewandelt.
Bezeichne den Druckvektor in Zeile \(i\) mit \(x_i\in \mathbb{F}_2^w\) und die Zielzeile des Bretts mit \(b_i\in \mathbb{F}_2^w\). Definiere die Breitenmatrix \(T_w\in \mathbb{F}_2^{w\times w}\) durch
$$T_w=\begin{pmatrix} 1 & 1 & 0 & \cdots & 0\\ 1 & 1 & 1 & \ddots & \vdots\\ 0 & 1 & 1 & \ddots & 0\\ \vdots & \ddots & \ddots & \ddots & 1\\ 0 & \cdots & 0 & 1 & 1 \end{pmatrix}.$$
Diese Matrix beschreibt den Effekt von Drücken innerhalb einer Zeile: das gedrückte Feld selbst sowie seine linken und rechten Nachbarn. Die vertikale Kopplung stammt von den Zeilen darüber und darunter, also gilt für Zeile \(i\)
$$x_{i-1}+T_w x_i+x_{i+1}=b_i,$$
mit Randbedingungen \(x_0=0\) und \(x_{h+1}=0\). Bezeichnet \(L_{w,h}\) den globalen Lights-Out-Operator, dann ist die Anzahl lösbarer Bretter die Größe seines Bildes:
$$F(w,h)=|\operatorname{Im}(L_{w,h})|=2^{\operatorname{rank}(L_{w,h})}.$$
Um die Bildgröße zu zählen, genügt die Dimension des Kerns. Im homogenen Fall \(b_i=0\) wird die Zeilenrelation zu
$$x_{i+1}=T_w x_i+x_{i-1}.$$
Nun definieren wir Matrixpolynome \(A_n\) durch
$$A_0=0,\qquad A_1=I,\qquad A_{n+2}=T_w A_{n+1}+A_n.$$
Beginnt man mit einem beliebigen Druckvektor \(x_1\) in der ersten Zeile, so liefert Induktion
$$x_i=A_i x_1\qquad (i\ge 0).$$
Die untere Randbedingung wird damit zu
$$A_{h+1}x_1=0.$$
Jedes Kern-Druckmuster wird also durch genau einen Vektor aus \(\ker(A_{h+1})\) bestimmt, und umgekehrt erzeugt jeder Vektor aus \(\ker(A_{h+1})\) ein gültiges homogenes Druckmuster. Daher
$$\dim\ker(L_{w,h})=\dim\ker(A_{h+1})=w-\operatorname{rank}(A_{h+1}).$$
Mit dem Dimensionssatz für den vollständigen Zugoperator mit \(wh\) Variablen folgt
$$\operatorname{rank}(L_{w,h})=wh-\left(w-\operatorname{rank}(A_{h+1})\right).$$
Also
$$F(w,h)=2^{wh-w+\operatorname{rank}(A_{h+1})}=2^{wh-\nu_{w,h}},$$
wobei \(\nu_{w,h}=w-\operatorname{rank}(A_{h+1})\) die relevante Nullität ist.
Jedes \(A_n\) ist ein Polynom in \(T_w\), daher kommutieren all diese Matrizen. Führe die Blockmatrix
$$M=\begin{pmatrix} T_w & I \\ I & 0 \end{pmatrix}$$
ein. Eine Standardinduktion zeigt
$$M^n=\begin{pmatrix} A_{n+1} & A_n \\ A_n & A_{n-1} \end{pmatrix}\qquad (n\ge 1).$$
Aus \(M^mM^n=M^{m+n}\) und dem Vergleich der Blöcke erhält man
$$A_{m+n+1}=A_{m+1}A_{n+1}+A_mA_n,$$
$$A_{m+n}=A_{m+1}A_n+A_mA_{n-1}.$$
Da in \(\mathbb{F}_2\) Addition und Subtraktion identisch sind, impliziert die Rekursion außerdem
$$A_{n-1}=T_wA_n+A_{n+1}.$$
Setzt man dies in die zweite Identität ein, erhält man genau die Form, die die Implementierung benutzt:
$$A_{m+n}=A_{m+1}A_n+A_mA_{n+1}+T_wA_mA_n.$$
Setze \(m=f_{k-1}\) und \(n=f_{k-2}\). Da \(f_k=m+n\) gilt, kann man mit den vorherigen Identitäten das Paar \((A_{f_k},A_{f_k+1})\) direkt aus den beiden vorherigen Fibonacci-Paaren berechnen:
$$A_{f_k}=A_{m+1}A_n+A_mA_{n+1}+T_wA_mA_n,$$
$$A_{f_k+1}=A_{m+1}A_{n+1}+A_mA_n.$$
Deshalb speichern die Implementierungen zwei aufeinanderfolgende Paare zu Fibonacci-Indizes, statt die Transferfolge für jede Höhe von Grund auf neu zu berechnen. Matrixmultiplikationen bleiben zwar nötig, aber die riesigen Lücken zwischen aufeinanderfolgenden Fibonacci-Zahlen werden übersprungen.
Sobald \(\operatorname{rank}(A_{h+1})\) bekannt ist, lautet der Beitrag zur Höhe \(h\)
$$F(w,h)=2^{wh-\left(w-\operatorname{rank}(A_{h+1})\right)}.$$
Die Endantwort wird modulo der Primzahl
$$p=10^9+7$$
berechnet. Nach dem kleinen Satz von Fermat darf der Exponent daher modulo
$$p-1=10^9+6$$
reduziert werden. Vor der modularen Potenzierung wird also nur \(wh-\nu_{w,h}\bmod (p-1)\) benötigt.
Für die Breite \(1\) ist die Zeilenmatrix einfach
$$T_1=[1].$$
Die Transferfolge ist dann
$$A_0=0,\qquad A_1=1,\qquad A_2=1,\qquad A_3=A_2+A_1=0.$$
Also hat \(A_{h+1}=A_3\) Rang \(0\) und damit Nullität \(1\). Das gesamte Brett besitzt \(wh=2\) Zellen, also
$$\operatorname{rank}(L_{1,2})=2-1=1.$$
Folglich
$$F(1,2)=2^1=2.$$
Das stimmt mit dem kleinen Kontrollwert der Implementierung überein. Anschaulich haben auf einem \(1\times 2\)-Brett beide Knöpfe denselben Effekt, daher sind nur das komplett dunkle und das komplett helle Brett lösbar.
Die C++-, Python- und Java-Implementierungen folgen demselben algebraischen Plan. Zuerst wird die Breitenmatrix einmal aufgebaut, dann wird jede Binärmatrix zeilenweise als gepackte Bits gespeichert, und XOR spielt die Rolle der Addition in \(\mathbb{F}_2\). Eine allgemeine Matrixmultiplikation läuft über die gesetzten Bits eines Faktors und verknüpft die passenden Zeilen des anderen Faktors per XOR. Die spezielle Multiplikation mit der tridiagonalen Breitenmatrix wird durch XOR mit der aktuellen Zeile und ihren direkten Nachbarzeilen erledigt.
Für die Endsumme hält die Implementierung stets zwei aufeinanderfolgende Fibonacci-Paare der Transferfolge bereit. Jeder neue Summand entsteht aus vier allgemeinen Matrixmultiplikationen, einer Anwendung der Breitenmatrix und einigen Matrix-XORs. Anschließend liefert Gauß-Elimination über \(\mathbb{F}_2\) den Rang der aktuellen Transfermatrix, die Nullität wird in den Exponenten \(wh-\nu\) umgerechnet, und schnelle modulare Potenzierung liefert den Beitrag zur laufenden Summe.
Für feste Breite \(w\) besitzt jede Matrix \(w\) Zeilen und \(\lceil w/64\rceil\) Maschinenwörter pro Zeile. Matrixaddition kostet \(O(w^2/64)\) Bitoperationen. Eine allgemeine Multiplikation oder eine gepackte Gauß-Elimination kostet ungefähr \(O(w^3/64)\) Bitoperationen. Für \(S(w,n)\) verwendet jeder neue Fibonacci-Term nur eine konstante Anzahl solcher Matrixoperationen. Daher beträgt die Gesamtlaufzeit \(O(nw^3/64)\), und der Speicherbedarf liegt bei \(O(w^2/64)\).
\(w\times h\) boyutlu bir Lights Out tahtasında bir hücreye basmak o hücreyi ve dört yönlü komşularını değiştirir. \(\mathbb{F}_2\) üzerinde iki kez basmak etkisiz olduğu için her basış düzeni ikili bir vektör olarak düşünülebilir ve problem lineer bir dönüşüme indirgenir. \(F(w,h)\), \(w\times h\) boyutundaki çözülebilir başlangıç tahtalarının sayısı olsun. İstenen büyüklük
$$S(w,n)=\sum_{k=1}^{n} F(w,f_k)\pmod{10^9+7},$$
burada \(f_1=f_2=1\) ve \(f_{k+1}=f_k+f_{k-1}\) Fibonacci dizisidir. Temel hızlandırma, tam \(wh\times wh\) oyun matrisini kurmak yerine problemi \(\mathbb{F}_2\) üzerinde \(w\times w\) matrislere indirgemektir.
Tahta satır satır işlenebilir. Böylece iki boyutlu Lights Out operatörü tek boyutlu bir transfer bağıntısına dönüşür.
\(i\). satırdaki basış vektörünü \(x_i\in \mathbb{F}_2^w\), hedef tahtanın aynı satırını ise \(b_i\in \mathbb{F}_2^w\) ile gösterelim. Genişlik matrisi \(T_w\in \mathbb{F}_2^{w\times w}\) şu olsun:
$$T_w=\begin{pmatrix} 1 & 1 & 0 & \cdots & 0\\ 1 & 1 & 1 & \ddots & \vdots\\ 0 & 1 & 1 & \ddots & 0\\ \vdots & \ddots & \ddots & \ddots & 1\\ 0 & \cdots & 0 & 1 & 1 \end{pmatrix}.$$
Bu matris aynı satır içindeki etkiyi anlatır: basılan hücre ve sol-sağ komşuları. Dikey etki ise üst ve alt satırlardan gelir; dolayısıyla \(i\). satır için
$$x_{i-1}+T_w x_i+x_{i+1}=b_i,$$
eşitliği vardır. Burada sınır koşulları \(x_0=0\) ve \(x_{h+1}=0\) şeklindedir. Tüm Lights Out operatörünü \(L_{w,h}\) ile gösterirsek çözülebilir tahtaların sayısı bu dönüşümün görüntü boyutudur:
$$F(w,h)=|\operatorname{Im}(L_{w,h})|=2^{\operatorname{rank}(L_{w,h})}.$$
Görüntü boyutunu saymak için çekirdeğin boyutunu bilmek yeterlidir. Homojen durumda \(b_i=0\) olduğunda satır bağıntısı
$$x_{i+1}=T_w x_i+x_{i-1}$$
olur. Şimdi \(A_n\) matris polinomlarını
$$A_0=0,\qquad A_1=I,\qquad A_{n+2}=T_w A_{n+1}+A_n$$
şeklinde tanımlayalım. İlk satırdaki basış vektörü \(x_1\) serbest seçilirse tümevarımla
$$x_i=A_i x_1\qquad (i\ge 0)$$
elde edilir. Alt sınır koşulu artık
$$A_{h+1}x_1=0$$
haline gelir. Böylece her çekirdek basış düzeni \(\ker(A_{h+1})\) içindeki tek bir vektör tarafından belirlenir ve tersine bu çekirdekteki her vektör geçerli bir homojen basış düzeni üretir. Sonuç olarak
$$\dim\ker(L_{w,h})=\dim\ker(A_{h+1})=w-\operatorname{rank}(A_{h+1}).$$
Tam \(wh\) değişkenli hamle operatörüne rank-nullity uygulandığında
$$\operatorname{rank}(L_{w,h})=wh-\left(w-\operatorname{rank}(A_{h+1})\right)$$
olur. Dolayısıyla
$$F(w,h)=2^{wh-w+\operatorname{rank}(A_{h+1})}=2^{wh-\nu_{w,h}},$$
burada \(\nu_{w,h}=w-\operatorname{rank}(A_{h+1})\) ilgili nullity değeridir.
Her \(A_n\), \(T_w\)'nin bir polinomudur; dolayısıyla bu matrislerin hepsi birbirleriyle değişmelidir. Şu blok matrisi tanımlayalım:
$$M=\begin{pmatrix} T_w & I \\ I & 0 \end{pmatrix}.$$
Standart bir tümevarım
$$M^n=\begin{pmatrix} A_{n+1} & A_n \\ A_n & A_{n-1} \end{pmatrix}\qquad (n\ge 1)$$
sonucunu verir. Şimdi \(M^mM^n=M^{m+n}\) yazıp blokları karşılaştırırsak
$$A_{m+n+1}=A_{m+1}A_{n+1}+A_mA_n,$$
$$A_{m+n}=A_{m+1}A_n+A_mA_{n-1}$$
elde edilir. \(\mathbb{F}_2\) içinde toplama ile çıkarma aynı olduğundan yinelemeli tanım ayrıca
$$A_{n-1}=T_wA_n+A_{n+1}$$
verir. Bunu ikinci özdeşliğe yerleştirince uygulamanın kullandığı biçim çıkar:
$$A_{m+n}=A_{m+1}A_n+A_mA_{n+1}+T_wA_mA_n.$$
\(m=f_{k-1}\) ve \(n=f_{k-2}\) olsun. \(f_k=m+n\) olduğundan önceki özdeşlikler \((A_{f_k},A_{f_k+1})\) çiftini doğrudan iki önceki Fibonacci çiftinden üretir:
$$A_{f_k}=A_{m+1}A_n+A_mA_{n+1}+T_wA_mA_n,$$
$$A_{f_k+1}=A_{m+1}A_{n+1}+A_mA_n.$$
Bu nedenle C++, Python ve Java uygulamaları her yükseklik için transfer dizisini baştan yürütmek yerine art arda gelen iki Fibonacci indisli çifti saklar. Yöntem hâlâ matris çarpımı kullanır, fakat ardışık Fibonacci sayıları arasındaki dev boşlukları atlamış olur.
\(\operatorname{rank}(A_{h+1})\) bilindiğinde yükseklik \(h\) için katkı
$$F(w,h)=2^{wh-\left(w-\operatorname{rank}(A_{h+1})\right)}$$
şeklindedir. Nihai cevap asal sayı
$$p=10^9+7$$
modunda alındığı için Fermat'nın küçük teoremi sayesinde üs
$$p-1=10^9+6$$
modunda indirgenebilir. Bu yüzden modüler üs alma öncesinde yalnızca \(wh-\nu_{w,h}\bmod (p-1)\) gerekir.
Genişlik \(1\) için satır matrisi
$$T_1=[1]$$
olur. Transfer dizisi de
$$A_0=0,\qquad A_1=1,\qquad A_2=1,\qquad A_3=A_2+A_1=0$$
şeklindedir. Dolayısıyla \(A_{h+1}=A_3\) matrisinin rank değeri \(0\), nullity değeri \(1\)'dir. Tam tahta \(wh=2\) hücre içerdiği için
$$\operatorname{rank}(L_{1,2})=2-1=1$$
elde edilir. Böylece
$$F(1,2)=2^1=2.$$
Bu, uygulamadaki küçük doğrulama değeriyle aynıdır. Sezgisel olarak \(1\times 2\) tahtada iki düğme de aynı etkiyi yaptığı için çözülebilir durumlar yalnızca tüm ışıklar kapalı ve tüm ışıklar açık tahtalardır.
C++, Python ve Java uygulamalarının üçü de aynı cebirsel planı uygular. Önce genişlik matrisi bir kez kurulur, sonra her ikili matris satır bazında paketlenmiş bitler olarak saklanır ve \(\mathbb{F}_2\) içindeki toplama işlemi XOR ile yapılır. Genel matris çarpımında bir çarpandaki 1 bitleri taranır ve diğer çarpandaki ilgili satırlar XOR'lanır. Tridiagonal genişlik matrisiyle olan özel çarpım ise her satırın kendisi ve komşu satırlarıyla XOR'lanmasıyla hesaplanır.
Son toplam için uygulama her zaman art arda gelen iki Fibonacci indisli transfer çiftini elde tutar. Her yeni terim dört genel matris çarpımı, genişlik matrisinin bir uygulanışı ve birkaç matris XOR işlemi ile üretilir. Daha sonra \(\mathbb{F}_2\) üzerinde Gauss eliminasyonu mevcut transfer matrisinin rank değerini bulur, buradan nullity ile üs \(wh-\nu\) hesaplanır ve hızlı modüler üs alma toplam içindeki katkıyı verir.
Sabit bir \(w\) genişliği için her matris \(w\) satır ve satır başına \(\lceil w/64\rceil\) makine kelimesi içerir. Matris toplama maliyeti \(O(w^2/64)\) bit işlemidir. Genel bir çarpım veya paketli Gauss eliminasyonu yaklaşık \(O(w^3/64)\) bit işlemi gerektirir. \(S(w,n)\) için her yeni Fibonacci terimi yalnızca sabit sayıda böyle matris işlemi yapar. Bu nedenle toplam çalışma süresi \(O(nw^3/64)\), bellek kullanımı ise \(O(w^2/64)\) olur.
En un tablero Lights Out de tamaño \(w\times h\), pulsar una celda cambia esa celda y sus vecinos ortogonales. Sobre \(\mathbb{F}_2\), pulsar dos veces cancela el efecto, así que cada patrón de pulsaciones es un vector binario y el rompecabezas completo se convierte en una aplicación lineal. Sea \(F(w,h)\) el número de tableros iniciales resolubles de tamaño \(w\times h\). La cantidad pedida es
$$S(w,n)=\sum_{k=1}^{n} F(w,f_k)\pmod{10^9+7},$$
donde \(f_1=f_2=1\) y \(f_{k+1}=f_k+f_{k-1}\). La optimización central consiste en evitar la matriz completa del juego de tamaño \(wh\times wh\) y reducir todo a matrices \(w\times w\) sobre \(\mathbb{F}_2\).
El tablero puede procesarse fila por fila. Eso transforma el operador bidimensional de Lights Out en una recurrencia de transferencia unidimensional.
Escribamos el vector de pulsaciones de la fila \(i\) como \(x_i\in \mathbb{F}_2^w\), y la fila objetivo del tablero como \(b_i\in \mathbb{F}_2^w\). Definimos la matriz de anchura \(T_w\in \mathbb{F}_2^{w\times w}\) por
$$T_w=\begin{pmatrix} 1 & 1 & 0 & \cdots & 0\\ 1 & 1 & 1 & \ddots & \vdots\\ 0 & 1 & 1 & \ddots & 0\\ \vdots & \ddots & \ddots & \ddots & 1\\ 0 & \cdots & 0 & 1 & 1 \end{pmatrix}.$$
Esta matriz describe el efecto dentro de una sola fila: la celda pulsada y sus vecinos izquierdo y derecho. La interacción vertical procede de las filas superior e inferior, así que la fila \(i\) satisface
$$x_{i-1}+T_w x_i+x_{i+1}=b_i,$$
con condiciones de borde \(x_0=0\) y \(x_{h+1}=0\). Si \(L_{w,h}\) es el operador global de Lights Out, entonces el número de tableros resolubles es el tamaño de su imagen:
$$F(w,h)=|\operatorname{Im}(L_{w,h})|=2^{\operatorname{rank}(L_{w,h})}.$$
Para contar el tamaño de la imagen basta conocer la dimensión del núcleo. En el caso homogéneo \(b_i=0\), la relación por filas se convierte en
$$x_{i+1}=T_w x_i+x_{i-1}.$$
Definimos ahora los polinomios matriciales \(A_n\) mediante
$$A_0=0,\qquad A_1=I,\qquad A_{n+2}=T_w A_{n+1}+A_n.$$
Partiendo de un vector arbitrario \(x_1\) en la primera fila, una inducción da
$$x_i=A_i x_1\qquad (i\ge 0).$$
La condición de borde inferior pasa a ser
$$A_{h+1}x_1=0.$$
Así, cada patrón de pulsaciones del núcleo queda determinado por un único vector de \(\ker(A_{h+1})\), y a la inversa todo vector de \(\ker(A_{h+1})\) produce un patrón homogéneo válido. Por tanto,
$$\dim\ker(L_{w,h})=\dim\ker(A_{h+1})=w-\operatorname{rank}(A_{h+1}).$$
Aplicando rango-nulidad al operador total con \(wh\) variables, obtenemos
$$\operatorname{rank}(L_{w,h})=wh-\left(w-\operatorname{rank}(A_{h+1})\right).$$
Luego
$$F(w,h)=2^{wh-w+\operatorname{rank}(A_{h+1})}=2^{wh-\nu_{w,h}},$$
donde \(\nu_{w,h}=w-\operatorname{rank}(A_{h+1})\) es la nulidad relevante.
Cada \(A_n\) es un polinomio en \(T_w\), así que todas estas matrices conmutan. Introducimos la matriz por bloques
$$M=\begin{pmatrix} T_w & I \\ I & 0 \end{pmatrix}.$$
Una inducción estándar muestra que
$$M^n=\begin{pmatrix} A_{n+1} & A_n \\ A_n & A_{n-1} \end{pmatrix}\qquad (n\ge 1).$$
Al multiplicar \(M^mM^n=M^{m+n}\) y comparar bloques se obtiene
$$A_{m+n+1}=A_{m+1}A_{n+1}+A_mA_n,$$
$$A_{m+n}=A_{m+1}A_n+A_mA_{n-1}.$$
Como en \(\mathbb{F}_2\) sumar y restar es lo mismo, la recurrencia también implica
$$A_{n-1}=T_wA_n+A_{n+1}.$$
Al sustituir esto en la segunda identidad aparece exactamente la forma usada por la implementación:
$$A_{m+n}=A_{m+1}A_n+A_mA_{n+1}+T_wA_mA_n.$$
Tomemos \(m=f_{k-1}\) y \(n=f_{k-2}\). Como \(f_k=m+n\), las identidades anteriores permiten calcular el par \((A_{f_k},A_{f_k+1})\) directamente a partir de los dos pares de Fibonacci anteriores:
$$A_{f_k}=A_{m+1}A_n+A_mA_{n+1}+T_wA_mA_n,$$
$$A_{f_k+1}=A_{m+1}A_{n+1}+A_mA_n.$$
Por eso las implementaciones guardan dos pares consecutivos con índices de Fibonacci, en lugar de reconstruir la sucesión de transferencia desde cero para cada altura. El método sigue usando multiplicación matricial, pero evita recorrer los enormes huecos entre números de Fibonacci consecutivos.
Una vez conocido \(\operatorname{rank}(A_{h+1})\), la contribución para la altura \(h\) es
$$F(w,h)=2^{wh-\left(w-\operatorname{rank}(A_{h+1})\right)}.$$
La respuesta final se toma módulo el primo
$$p=10^9+7.$$
Por el pequeño teorema de Fermat, el exponente puede reducirse módulo
$$p-1=10^9+6,$$
de modo que antes de la exponenciación modular sólo hace falta \(wh-\nu_{w,h}\bmod (p-1)\).
Para anchura \(1\), la matriz de fila es simplemente
$$T_1=[1].$$
La sucesión de transferencia queda
$$A_0=0,\qquad A_1=1,\qquad A_2=1,\qquad A_3=A_2+A_1=0.$$
Así, \(A_{h+1}=A_3\) tiene rango \(0\) y por tanto nulidad \(1\). El tablero completo tiene \(wh=2\) celdas, luego
$$\operatorname{rank}(L_{1,2})=2-1=1.$$
En consecuencia,
$$F(1,2)=2^1=2.$$
Esto coincide con la pequeña comprobación usada por la implementación. De forma concreta, en un tablero \(1\times 2\) ambos botones producen el mismo efecto, así que los únicos estados resolubles son el tablero completamente apagado y el completamente encendido.
Las implementaciones en C++, Python y Java siguen exactamente el mismo plan algebraico. Construyen la matriz de anchura una sola vez, guardan cada fila binaria como bits empaquetados y usan XOR como suma en \(\mathbb{F}_2\). La multiplicación matricial general recorre los bits activos de un factor y hace XOR con las filas correspondientes del otro factor. La multiplicación especial por la matriz tridiagonal de anchura se resuelve haciendo XOR de cada fila con ella misma y con sus vecinas inmediatas.
Para la suma final, la implementación mantiene dos pares consecutivos de la sucesión de transferencia en índices de Fibonacci. Cada término nuevo se obtiene mediante cuatro multiplicaciones matriciales generales, una aplicación de la matriz de anchura y unas pocas sumas XOR de matrices. Después, la eliminación de Gauss sobre \(\mathbb{F}_2\) da el rango de la matriz de transferencia actual, la nulidad se transforma en el exponente \(wh-\nu\), y una exponenciación modular rápida produce la contribución al acumulado.
Para anchura fija \(w\), cada matriz tiene \(w\) filas y \(\lceil w/64\rceil\) palabras de máquina por fila. La suma de matrices cuesta \(O(w^2/64)\) operaciones de bits. Una multiplicación general o una eliminación de Gauss empaquetada cuesta aproximadamente \(O(w^3/64)\) operaciones de bits. En \(S(w,n)\), cada nuevo término de Fibonacci realiza sólo un número constante de esas operaciones, así que el tiempo total es \(O(nw^3/64)\) y la memoria es \(O(w^2/64)\).
在一个 \(w\times h\) 的 Lights Out 棋盘上，按下一个格子会翻转该格子以及它的上下左右邻格。由于在 \(\mathbb{F}_2\) 上按两次等于不按，所以每一种按键方案都可以看成一个二进制向量，整个谜题因此变成一个线性映射。记 \(F(w,h)\) 为大小为 \(w\times h\) 的可解初始棋盘个数。题目要求计算
$$S(w,n)=\sum_{k=1}^{n} F(w,f_k)\pmod{10^9+7},$$
其中 \(f_1=f_2=1\)，且 \(f_{k+1}=f_k+f_{k-1}\)。核心优化在于不去构造完整的 \(wh\times wh\) 游戏矩阵，而是把问题压缩成 \(\mathbb{F}_2\) 上的 \(w\times w\) 矩阵递推。
关键观察是可以按行处理棋盘。这样二维的 Lights Out 算子就会转化为一维的传递递推。
把第 \(i\) 行的按键向量记为 \(x_i\in \mathbb{F}_2^w\)，把目标棋盘的第 \(i\) 行记为 \(b_i\in \mathbb{F}_2^w\)。定义宽度矩阵 \(T_w\in \mathbb{F}_2^{w\times w}\) 为
$$T_w=\begin{pmatrix} 1 & 1 & 0 & \cdots & 0\\ 1 & 1 & 1 & \ddots & \vdots\\ 0 & 1 & 1 & \ddots & 0\\ \vdots & \ddots & \ddots & \ddots & 1\\ 0 & \cdots & 0 & 1 & 1 \end{pmatrix}.$$
这个矩阵刻画同一行内部的影响，也就是被按下的格子及其左右邻格。竖直方向的影响来自上一行和下一行，因此第 \(i\) 行满足
$$x_{i-1}+T_w x_i+x_{i+1}=b_i,$$
边界条件为 \(x_0=0\) 与 \(x_{h+1}=0\)。若把整个 Lights Out 操作记为 \(L_{w,h}\)，那么可解棋盘的数量就是这个线性映射像空间的大小：
$$F(w,h)=|\operatorname{Im}(L_{w,h})|=2^{\operatorname{rank}(L_{w,h})}.$$
要计算像空间大小，只需要知道核空间维数。在齐次情形 \(b_i=0\) 下，行之间的关系变成
$$x_{i+1}=T_w x_i+x_{i-1}.$$
现在定义矩阵序列 \(A_n\)：
$$A_0=0,\qquad A_1=I,\qquad A_{n+2}=T_w A_{n+1}+A_n.$$
若第一行按键向量 \(x_1\) 任意给定，则由归纳法可得
$$x_i=A_i x_1\qquad (i\ge 0).$$
底部边界条件于是变成
$$A_{h+1}x_1=0.$$
也就是说，每一个核中的按键方案都由 \(\ker(A_{h+1})\) 中的一个向量唯一决定；反过来，\(\ker(A_{h+1})\) 中的每个向量也都会生成一个合法的齐次按键方案。因此
$$\dim\ker(L_{w,h})=\dim\ker(A_{h+1})=w-\operatorname{rank}(A_{h+1}).$$
再对拥有 \(wh\) 个变量的完整操作应用秩-零化度定理，就得到
$$\operatorname{rank}(L_{w,h})=wh-\left(w-\operatorname{rank}(A_{h+1})\right).$$
从而
$$F(w,h)=2^{wh-w+\operatorname{rank}(A_{h+1})}=2^{wh-\nu_{w,h}},$$
其中 \(\nu_{w,h}=w-\operatorname{rank}(A_{h+1})\) 是这里真正需要的零空间维数。
每个 \(A_n\) 都是 \(T_w\) 的多项式，因此这些矩阵彼此可交换。引入分块矩阵
$$M=\begin{pmatrix} T_w & I \\ I & 0 \end{pmatrix}.$$
标准归纳可得
$$M^n=\begin{pmatrix} A_{n+1} & A_n \\ A_n & A_{n-1} \end{pmatrix}\qquad (n\ge 1).$$
把 \(M^mM^n=M^{m+n}\) 展开并比较各个分块，就得到
$$A_{m+n+1}=A_{m+1}A_{n+1}+A_mA_n,$$
$$A_{m+n}=A_{m+1}A_n+A_mA_{n-1}.$$
由于在 \(\mathbb{F}_2\) 中加法与减法相同，递推式还推出
$$A_{n-1}=T_wA_n+A_{n+1}.$$
把它代入第二个恒等式，就得到实现里真正使用的形式：
$$A_{m+n}=A_{m+1}A_n+A_mA_{n+1}+T_wA_mA_n.$$
令 \(m=f_{k-1}\)、\(n=f_{k-2}\)。因为 \(f_k=m+n\)，上面的恒等式就允许我们直接由前两个 Fibonacci 下标的矩阵对，计算出新的矩阵对 \((A_{f_k},A_{f_k+1})\)：
$$A_{f_k}=A_{m+1}A_n+A_mA_{n+1}+T_wA_mA_n,$$
$$A_{f_k+1}=A_{m+1}A_{n+1}+A_mA_n.$$
这就是实现为什么只保存两个相邻的 Fibonacci 下标矩阵对，而不是对每个高度都从头推进整个传递序列。算法依然需要做矩阵乘法，但它跳过了相邻 Fibonacci 数之间极其巨大的空档。
一旦 \(\operatorname{rank}(A_{h+1})\) 已知，对应高度 \(h\) 的贡献就是
$$F(w,h)=2^{wh-\left(w-\operatorname{rank}(A_{h+1})\right)}.$$
最终答案要对素数
$$p=10^9+7$$
取模。根据费马小定理，指数可以先对
$$p-1=10^9+6$$
取模，因此在做模幂之前，只需要保留 \(wh-\nu_{w,h}\bmod (p-1)\)。
当宽度为 \(1\) 时，行矩阵只有
$$T_1=[1].$$
此时传递序列为
$$A_0=0,\qquad A_1=1,\qquad A_2=1,\qquad A_3=A_2+A_1=0.$$
所以 \(A_{h+1}=A_3\) 的秩为 \(0\)，零空间维数为 \(1\)。整个棋盘共有 \(wh=2\) 个格子，因此
$$\operatorname{rank}(L_{1,2})=2-1=1.$$
于是
$$F(1,2)=2^1=2.$$
这与实现中的小型校验值一致。直观地说，在 \(1\times 2\) 棋盘上两个按钮造成的翻转完全相同，所以可解状态只有全灭和全亮两种。
C++、Python 和 Java 三份实现采用同一套代数思路。它们先构造宽度矩阵，再把每个二进制矩阵按行存成打包位串，并且用 XOR 作为 \(\mathbb{F}_2\) 上的加法。一般矩阵乘法会扫描一个因子中的 1 位，然后把另一个因子里对应的整行做 XOR；而与三对角宽度矩阵的特殊相乘，则通过把每一行与自身及其相邻两行做 XOR 来完成。
在最终求和阶段，实现始终维护两个相邻的 Fibonacci 下标传递矩阵对。每生成一个新项，需要四次一般矩阵乘法、一次宽度矩阵作用以及少量矩阵 XOR。随后在 \(\mathbb{F}_2\) 上做高斯消元，得到当前传递矩阵的秩，再把对应的零空间维数转成指数 \(wh-\nu\)，最后用快速模幂把这一项加入总和。
在固定宽度 \(w\) 下，每个矩阵有 \(w\) 行，每行占用 \(\lceil w/64\rceil\) 个机器字。矩阵加法需要 \(O(w^2/64)\) 位运算。一次一般矩阵乘法或一次打包的高斯消元大约需要 \(O(w^3/64)\) 位运算。对于 \(S(w,n)\)，每个新的 Fibonacci 项只做常数次这样的矩阵操作，因此总时间复杂度为 \(O(nw^3/64)\)，空间复杂度为 \(O(w^2/64)\)。
На доске Lights Out размера \(w\times h\) нажатие на клетку переключает эту клетку и её ортогональных соседей. Над \(\mathbb{F}_2\) двойное нажатие сокращается, поэтому любой набор нажатий является бинарным вектором, а вся задача превращается в линейное отображение. Обозначим через \(F(w,h)\) число разрешимых начальных досок размера \(w\times h\). Требуется вычислить
$$S(w,n)=\sum_{k=1}^{n} F(w,f_k)\pmod{10^9+7},$$
где \(f_1=f_2=1\) и \(f_{k+1}=f_k+f_{k-1}\). Главная оптимизация состоит в том, чтобы не строить полную игровую матрицу размера \(wh\times wh\), а свести всё к матрицам размера \(w\times w\) над \(\mathbb{F}_2\).
Доску удобно обрабатывать по строкам. Тогда двумерный оператор Lights Out превращается в одномерную передаточную рекурсию.
Пусть вектор нажатий в строке \(i\) равен \(x_i\in \mathbb{F}_2^w\), а соответствующая строка целевой доски равна \(b_i\in \mathbb{F}_2^w\). Определим матрицу ширины \(T_w\in \mathbb{F}_2^{w\times w}\) так:
$$T_w=\begin{pmatrix} 1 & 1 & 0 & \cdots & 0\\ 1 & 1 & 1 & \ddots & \vdots\\ 0 & 1 & 1 & \ddots & 0\\ \vdots & \ddots & \ddots & \ddots & 1\\ 0 & \cdots & 0 & 1 & 1 \end{pmatrix}.$$
Эта матрица описывает влияние нажатий внутри одной строки: сама клетка и её левые и правые соседи. Вертикальная связь приходит из строк сверху и снизу, поэтому для строки \(i\) выполняется
$$x_{i-1}+T_w x_i+x_{i+1}=b_i,$$
при граничных условиях \(x_0=0\) и \(x_{h+1}=0\). Если обозначить глобальный оператор Lights Out через \(L_{w,h}\), то число разрешимых досок равно размеру его образа:
$$F(w,h)=|\operatorname{Im}(L_{w,h})|=2^{\operatorname{rank}(L_{w,h})}.$$
Чтобы посчитать размер образа, достаточно знать размерность ядра. В однородном случае \(b_i=0\) строковое соотношение принимает вид
$$x_{i+1}=T_w x_i+x_{i-1}.$$
Теперь введём матричную последовательность \(A_n\):
$$A_0=0,\qquad A_1=I,\qquad A_{n+2}=T_w A_{n+1}+A_n.$$
Если первый вектор нажатий \(x_1\) выбран произвольно, то по индукции получаем
$$x_i=A_i x_1\qquad (i\ge 0).$$
Нижнее граничное условие превращается в
$$A_{h+1}x_1=0.$$
Значит, каждый шаблон нажатий из ядра однозначно задаётся вектором из \(\ker(A_{h+1})\), и наоборот любой вектор из \(\ker(A_{h+1})\) создаёт допустимый однородный шаблон. Следовательно,
$$\dim\ker(L_{w,h})=\dim\ker(A_{h+1})=w-\operatorname{rank}(A_{h+1}).$$
Применяя теорему о ранге и дефекте к полному оператору с \(wh\) переменными, получаем
$$\operatorname{rank}(L_{w,h})=wh-\left(w-\operatorname{rank}(A_{h+1})\right).$$
Поэтому
$$F(w,h)=2^{wh-w+\operatorname{rank}(A_{h+1})}=2^{wh-\nu_{w,h}},$$
где \(\nu_{w,h}=w-\operatorname{rank}(A_{h+1})\) — нужная нулевость.
Каждая матрица \(A_n\) является полиномом от \(T_w\), поэтому все такие матрицы коммутируют. Введём блочную матрицу
$$M=\begin{pmatrix} T_w & I \\ I & 0 \end{pmatrix}.$$
Стандартная индукция даёт
$$M^n=\begin{pmatrix} A_{n+1} & A_n \\ A_n & A_{n-1} \end{pmatrix}\qquad (n\ge 1).$$
Из равенства \(M^mM^n=M^{m+n}\) и сравнения блоков следует
$$A_{m+n+1}=A_{m+1}A_{n+1}+A_mA_n,$$
$$A_{m+n}=A_{m+1}A_n+A_mA_{n-1}.$$
Поскольку в \(\mathbb{F}_2\) сложение совпадает с вычитанием, рекурсия также даёт
$$A_{n-1}=T_wA_n+A_{n+1}.$$
Подстановка в вторую формулу приводит к форме, используемой в реализации:
$$A_{m+n}=A_{m+1}A_n+A_mA_{n+1}+T_wA_mA_n.$$
Положим \(m=f_{k-1}\) и \(n=f_{k-2}\). Так как \(f_k=m+n\), предыдущие тождества позволяют напрямую вычислить пару \((A_{f_k},A_{f_k+1})\) из двух предыдущих пар на индексах Фибоначчи:
$$A_{f_k}=A_{m+1}A_n+A_mA_{n+1}+T_wA_mA_n,$$
$$A_{f_k+1}=A_{m+1}A_{n+1}+A_mA_n.$$
Именно поэтому реализации хранят две соседние пары на индексах Фибоначчи, а не перестраивают передаточную последовательность с нуля для каждой высоты. Матричные умножения всё равно нужны, но огромные промежутки между соседними числами Фибоначчи при этом пропускаются.
Когда \(\operatorname{rank}(A_{h+1})\) уже известен, вклад высоты \(h\) равен
$$F(w,h)=2^{wh-\left(w-\operatorname{rank}(A_{h+1})\right)}.$$
Окончательный ответ берётся по модулю простого числа
$$p=10^9+7.$$
По малой теореме Ферма показатель можно сократить по модулю
$$p-1=10^9+6,$$
поэтому перед быстрым возведением в степень нужен только \(wh-\nu_{w,h}\bmod (p-1)\).
При ширине \(1\) матрица строки имеет вид
$$T_1=[1].$$
Передаточная последовательность равна
$$A_0=0,\qquad A_1=1,\qquad A_2=1,\qquad A_3=A_2+A_1=0.$$
Следовательно, \(A_{h+1}=A_3\) имеет ранг \(0\), а нулевость равна \(1\). На всей доске \(wh=2\) клетки, значит
$$\operatorname{rank}(L_{1,2})=2-1=1.$$
Тем самым
$$F(1,2)=2^1=2.$$
Это совпадает с малой проверкой в реализации. Интуитивно на доске \(1\times 2\) обе кнопки действуют одинаково, поэтому разрешимы только полностью тёмное и полностью освещённое состояния.
Реализации на C++, Python и Java используют один и тот же алгебраический план. Сначала строится матрица ширины, затем каждая бинарная матрица хранится построчно в упакованном виде, а роль сложения в \(\mathbb{F}_2\) играет XOR. Общее матричное умножение проходит по установленным битам одного множителя и XOR'ит соответствующие строки другого множителя. Специальное умножение на трёхдиагональную матрицу ширины выполняется с помощью XOR текущей строки с самой собой и соседними строками.
Для итоговой суммы реализация поддерживает две последовательные пары передаточных матриц на индексах Фибоначчи. Каждый новый член получается из четырёх обычных матричных умножений, одного применения матрицы ширины и нескольких операций XOR над матрицами. После этого метод Гаусса над \(\mathbb{F}_2\) даёт ранг текущей передаточной матрицы, нулевость превращается в показатель \(wh-\nu\), а быстрое модульное возведение в степень даёт вклад в накопленную сумму.
При фиксированной ширине \(w\) каждая матрица содержит \(w\) строк и \(\lceil w/64\rceil\) машинных слов в строке. Сложение матриц стоит \(O(w^2/64)\) битовых операций. Одно общее умножение или упакованный метод Гаусса требуют примерно \(O(w^3/64)\) битовых операций. Для \(S(w,n)\) каждый новый член на индексе Фибоначчи делает лишь константное число таких матричных операций. Поэтому полная трудоёмкость равна \(O(nw^3/64)\), а память — \(O(w^2/64)\).
على لوحة Lights Out ذات الأبعاد \(w\times h\)، يؤدي الضغط على خلية إلى قلب حالة تلك الخلية وجيرانها المتعامدين. وبما أن العمل يتم فوق \(\mathbb{F}_2\)، فإن الضغط مرتين يلغي نفسه، لذلك يمكن تمثيل كل نمط ضغط بمتجه ثنائي وتتحول المسألة كلها إلى تحويل خطي. نرمز بـ \(F(w,h)\) إلى عدد الألواح الابتدائية القابلة للحل ذات الحجم \(w\times h\). والكمية المطلوبة هي
$$S(w,n)=\sum_{k=1}^{n} F(w,f_k)\pmod{10^9+7},$$
حيث \(f_1=f_2=1\) و \(f_{k+1}=f_k+f_{k-1}\). الفكرة الأساسية هي تجنب بناء مصفوفة اللعبة الكاملة ذات الحجم \(wh\times wh\)، واختزال كل شيء إلى مصفوفات \(w\times w\) فوق \(\mathbb{F}_2\).
يمكن معالجة اللوحة صفًا صفًا. وبهذه الطريقة يتحول مؤثر Lights Out ثنائي الأبعاد إلى علاقة انتقال أحادية البعد.
لنكتب متجه الضغط في الصف \(i\) على صورة \(x_i\in \mathbb{F}_2^w\)، ولنكتب صف الهدف في اللوحة على صورة \(b_i\in \mathbb{F}_2^w\). نعرّف مصفوفة العرض \(T_w\in \mathbb{F}_2^{w\times w}\) كما يلي:
$$T_w=\begin{pmatrix} 1 & 1 & 0 & \cdots & 0\\ 1 & 1 & 1 & \ddots & \vdots\\ 0 & 1 & 1 & \ddots & 0\\ \vdots & \ddots & \ddots & \ddots & 1\\ 0 & \cdots & 0 & 1 & 1 \end{pmatrix}.$$
هذه المصفوفة تصف التأثير داخل الصف نفسه: الخلية المضغوطة وجاراها الأيسر والأيمن. أما التأثير الرأسي فيأتي من الصفين الأعلى والأسفل، ولذلك يحقق الصف \(i\) العلاقة
$$x_{i-1}+T_w x_i+x_{i+1}=b_i,$$
مع الشرطين الحدّيين \(x_0=0\) و \(x_{h+1}=0\). وإذا رمزنا إلى مؤثر Lights Out الكلي بـ \(L_{w,h}\)، فإن عدد الألواح القابلة للحل يساوي حجم صورته:
$$F(w,h)=|\operatorname{Im}(L_{w,h})|=2^{\operatorname{rank}(L_{w,h})}.$$
لحساب حجم الصورة يكفي معرفة بُعد النواة. في الحالة المتجانسة \(b_i=0\) تصبح علاقة الصفوف
$$x_{i+1}=T_w x_i+x_{i-1}.$$
نعرّف الآن المتتالية المصفوفية \(A_n\) بالصيغة
$$A_0=0,\qquad A_1=I,\qquad A_{n+2}=T_w A_{n+1}+A_n.$$
إذا اخترنا متجه الضغط الأول \(x_1\) بحرية، فإن الاستقراء يعطي
$$x_i=A_i x_1\qquad (i\ge 0).$$
وبذلك يتحول الشرط الحدّي السفلي إلى
$$A_{h+1}x_1=0.$$
إذن كل نمط ضغط ينتمي إلى النواة يتحدد بمتجه واحد من \(\ker(A_{h+1})\)، وبالعكس فإن كل متجه في \(\ker(A_{h+1})\) يولد نمط ضغط متجانسًا صالحًا. ومن ثم
$$\dim\ker(L_{w,h})=\dim\ker(A_{h+1})=w-\operatorname{rank}(A_{h+1}).$$
وبتطبيق مبرهنة الرتبة-النواة على المؤثر الكامل ذي \(wh\) متغيرًا نحصل على
$$\operatorname{rank}(L_{w,h})=wh-\left(w-\operatorname{rank}(A_{h+1})\right).$$
ومن هنا
$$F(w,h)=2^{wh-w+\operatorname{rank}(A_{h+1})}=2^{wh-\nu_{w,h}},$$
حيث \(\nu_{w,h}=w-\operatorname{rank}(A_{h+1})\) هي قيمة النواة المطلوبة فعلًا.
كل \(A_n\) هو كثير حدود في \(T_w\)، ولذلك فإن هذه المصفوفات كلها تتبادل. نعرّف المصفوفة الكتلية
$$M=\begin{pmatrix} T_w & I \\ I & 0 \end{pmatrix}.$$
ويعطي الاستقراء القياسي
$$M^n=\begin{pmatrix} A_{n+1} & A_n \\ A_n & A_{n-1} \end{pmatrix}\qquad (n\ge 1).$$
وبضرب \(M^mM^n=M^{m+n}\) ثم مقارنة الكتل نحصل على
$$A_{m+n+1}=A_{m+1}A_{n+1}+A_mA_n,$$
$$A_{m+n}=A_{m+1}A_n+A_mA_{n-1}.$$
ولأن الجمع والطرح متماثلان في \(\mathbb{F}_2\)، فإن علاقة التكرار تعطي أيضًا
$$A_{n-1}=T_wA_n+A_{n+1}.$$
وبالتعويض في الهوية الثانية نحصل على الصيغة المستخدمة في التنفيذ:
$$A_{m+n}=A_{m+1}A_n+A_mA_{n+1}+T_wA_mA_n.$$
لنضع \(m=f_{k-1}\) و \(n=f_{k-2}\). بما أن \(f_k=m+n\)، فإن الهويات السابقة تسمح بحساب الزوج \((A_{f_k},A_{f_k+1})\) مباشرة من الزوجين السابقين الموافقين لمؤشري فيبوناتشي:
$$A_{f_k}=A_{m+1}A_n+A_mA_{n+1}+T_wA_mA_n,$$
$$A_{f_k+1}=A_{m+1}A_{n+1}+A_mA_n.$$
ولهذا تحتفظ التطبيقات بزوجين متتاليين عند مؤشرات فيبوناتشي بدلًا من إعادة بناء متتالية الانتقال من البداية لكل ارتفاع. ما زالت هناك ضربات مصفوفية، لكن يتم تجاوز الفجوات الهائلة بين أعداد فيبوناتشي المتتالية.
بعد معرفة \(\operatorname{rank}(A_{h+1})\)، يصبح إسهام الارتفاع \(h\) هو
$$F(w,h)=2^{wh-\left(w-\operatorname{rank}(A_{h+1})\right)}.$$
الجواب النهائي يؤخذ بترديد العدد الأولي
$$p=10^9+7.$$
وبحسب مبرهنة فيرما الصغرى يمكن اختزال الأسّ بترديد
$$p-1=10^9+6,$$
ولذلك لا نحتاج قبل الأسّ المعياري إلا إلى \(wh-\nu_{w,h}\bmod (p-1)\).
عندما يكون العرض \(1\)، تصبح مصفوفة الصف
$$T_1=[1].$$
وعندئذ تكون متتالية الانتقال
$$A_0=0,\qquad A_1=1,\qquad A_2=1,\qquad A_3=A_2+A_1=0.$$
إذًا للمصفوفة \(A_{h+1}=A_3\) رتبة تساوي \(0\)، ومن ثم نواة بعدُها \(1\). وبما أن اللوحة كلها تحتوي على \(wh=2\) خلية، فإن
$$\operatorname{rank}(L_{1,2})=2-1=1.$$
وعليه
$$F(1,2)=2^1=2.$$
وهذا يطابق نقطة التحقق الصغيرة في التنفيذ. وبصورة ملموسة، على لوحة \(1\times 2\) يكون للزرين التأثير نفسه، لذلك فإن الحالتين القابلتين للحل فقط هما اللوحة المطفأة بالكامل واللوحة المضاءة بالكامل.
تتبع تطبيقات C++ وPython وJava الخطة الجبرية نفسها. فهي تبني مصفوفة العرض مرة واحدة، ثم تخزن كل صف من كل مصفوفة ثنائية على شكل بتات مضغوطة، وتستخدم XOR بوصفه عملية الجمع في \(\mathbb{F}_2\). في الضرب المصفوفي العام يتم المرور على البتات المفعلة في أحد العاملين ثم إجراء XOR للصفوف الموافقة في العامل الآخر. أما الضرب الخاص بمصفوفة العرض الثلاثية القطر فيتم بواسطة XOR كل صف مع نفسه ومع جاريه المباشرين.
وفي الجمع النهائي تحتفظ الشيفرة دائمًا بزوجين متتاليين من مصفوفات الانتقال عند مؤشرات فيبوناتشي. كل حد جديد يُنتج عبر أربع ضربات مصفوفية عامة، وتطبيق واحد لمصفوفة العرض، وعدة عمليات XOR بين المصفوفات. بعد ذلك تعطي عملية الحذف الغاوسي فوق \(\mathbb{F}_2\) رتبة مصفوفة الانتقال الحالية، وتتحول النواة إلى الأسّ \(wh-\nu\)، ثم يعطي الأسّ المعياري السريع قيمة الإسهام الذي يضاف إلى المجموع.
عند تثبيت العرض \(w\)، تحتوي كل مصفوفة على \(w\) صفوف و \(\lceil w/64\rceil\) كلمات آلة في كل صف. كلفة جمع المصفوفات هي \(O(w^2/64)\) من عمليات البت. أما الضرب العام أو الحذف الغاوسي المضغوط فتكلفتهما نحو \(O(w^3/64)\) من عمليات البت. وفي \(S(w,n)\) يحتاج كل حد جديد من حدود فيبوناتشي إلى عدد ثابت فقط من هذه العمليات، لذلك يكون الزمن الكلي \(O(nw^3/64)\)، بينما يكون استهلاك الذاكرة \(O(w^2/64)\).