Detailed mathematical approach

Problem Summary

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\).

Mathematical Approach

The board can be processed row by row. This turns the two-dimensional Lights Out operator into a one-dimensional transfer recurrence.

Step 1: Encode One Row by a Width Matrix

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})}.$

Step 2: Reduce the Kernel to a Transfer Sequence

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.

Step 3: Derive Addition Formulas for the Sequence

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.$

Step 4: Jump Directly Along Fibonacci Heights

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.

Step 5: Convert Rank to the Required Modular Value

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.

Worked Example: \(w=1,\ h=2\)

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.

How the Code Works

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.

Complexity Analysis

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)\).

Footnotes and References

1. Problem page: https://projecteuler.net/problem=707
2. Lights Out: Wikipedia — Lights Out
3. Rank-nullity theorem: Wikipedia — Rank-nullity theorem
4. Gaussian elimination: Wikipedia — Gaussian elimination
5. Fibonacci numbers: Wikipedia — Fibonacci number