← 完整题目索引

PROJECT EULER · #0707

熄灯

Lights Out

仅题目 · 待解原题 ↗

考虑 w×h 网格。单元格要么打开,要么关闭。当选择一个单元格时,该单元格以及通过边缘连接到该单元格的所有单元格都会在开-关、关-开之间切换。请参阅图表,了解在所有单元格均亮起(白色)的网格中选择角单元格、边缘单元格或中心单元格的 3 种情况。

LightsOut

目标是让每个单元同时关闭。这对于所有起始状态都是不可能的。如果通过选择单元的过程可以实现目标,则状态是可解的。

设 F(w,h) 为 w×h 网格的可解状态数。 给定 F(1,2)=2、F(3,3)=512、F(4,4)=4096 和 F(7,11)≡270016253(mod1000000007)。

设 f1=f2=1 和 fn=fn−1+fn−2,n≥3 为斐波那契数列并定义 S(w,n)=∑k=1nF(w,fk) 给定 S(3,3)=32、S(4,5)=1052960 和 S(5,7)≡346547294(mod1000000007)。

查找 S(199,199)。以 1000000007 为模给出你的答案。

题解待补充

这道题的题目已收录,解题思路、代码和答案将在后续补充。