Project Euler Problem 707
Consider a wtimes h grid.
Solution
Answer: 652907799
Let $A_{w,h}$ be the Lights Out matrix over $\mathbb F_2$.
The number of solvable states is
$$F(w,h)=2^{\operatorname{rank}(A_{w,h})}.$$
For the rectangular grid, a standard result gives
$$\dim \ker(A_{w,h}) = \deg \gcd(P_w(x), P_h(x+1)),$$
where the polynomials $P_n$ over $\mathbb F_2$ satisfy
$$P_0=1,\qquad P_1=x,\qquad P_n=xP_{n-1}+P_{n-2}.$$
Hence
$$F(w,h)=2^{wh-d(w,h)}, \qquad d(w,h)=\deg \gcd(P_w(x),P_h(x+1)).$$
For this problem we need
$$S(199,199)=\sum_{k=1}^{199}F(199,f_k),$$
with $f_k$ Fibonacci numbers.
The computation can be done efficiently by:
- representing polynomials over $\mathbb F_2$ as bitsets,
- computing $P_{199}$,
- evaluating $P_n(x+1)\bmod P_{199}$ via fast matrix exponentiation,
- taking polynomial gcd degrees,
- summing $2^{199f_k-d}\pmod{10^9+7}$.
The implementation reproduces the checks:
- $S(3,3)=32$,
- $S(4,5)=1052960$,
- $S(5,7)\equiv346547294\pmod{10^9+7}$.
The final computation gives:
Answer: 652907799