问题分析

我们面对的是一个在 $2^n \times 2^n$ 的环面网格上的开关反转问题。每个格子有两种状态（白/黑，对应 0/1），初始全为白色。每次操作选择一个格子，反转该格子及其上下左右四个相邻格子的颜色（在环面拓扑下，边界是循环连接的）。

给定目标图案（一个 0/1 矩阵），我们需要找到一系列操作位置，使得最终网格状态与目标图案一致，或者判断无解。

---

核心难点

1. 环面拓扑

网格的第一行与最后一行相邻，第一列与最后一列相邻。这意味着：

• 对于位置 $(0, j)$，其"上"邻居是 $(2^n-1, j)$
• 对于位置 $(2^n-1, j)$，其"下"邻居是 $(0, j)$
• 列方向同理

这使得问题具有周期性边界条件，影响了每个操作影响的格子模式。

2. 操作的可逆性

每次操作是异或（模 2 加法）：

• 颜色反转：状态 $s \rightarrow s \oplus 1$
• 两次相同操作抵消：操作是自逆的（在模 2 下，操作两次等于没操作）
• 操作顺序无关紧要：因为异或满足交换律和结合律

3. 问题规模

$n \leq 11$，网格大小 $N = 2^n \leq 2048$，总格子数 $N^2 \leq 4,\!194,\!304$。 直接枚举每个格子是否操作有 $2^{N^2}$ 种可能，显然不可行。

---

数学模型建立

1. 变量定义

设 $x_{ij} \in \{0, 1\}$ 表示格子 $(i, j)$ 是否被操作（1 表示操作，0 表示不操作）。

2. 影响矩阵

一次操作影响自身和四个邻居。在环面拓扑下，对于格子 $(i, j)$，其最终状态为： $ \text{最终状态}_{ij} = \left( \sum_{\text{(i,j)及其邻居}} x_{\text{邻居}} \right) \bmod 2 $ 因为初始全为 0（白色），而我们要达到目标 $T_{ij} \in \{0, 1\}$，所以： $ \left( x_{ij} + x_{i-1,j} + x_{i+1,j} + x_{i,j-1} + x_{i,j+1} \right) \bmod 2 = T_{ij} $ 其中下标运算在模 $N$ 意义下（$N = 2^n$）。

3. 线性方程组

上述方程对每个 $(i, j)$ 成立，共 $N^2$ 个方程，$N^2$ 个未知数 $x_{ij}$，系数在 $\mathbb{F}_2$（二元域）中。

写成矩阵形式： $A \mathbf{x} = \mathbf{t} \quad (\text{模 } 2)$ 其中：

• $A$ 是 $N^2 \times N^2$ 的系数矩阵
• $\mathbf{x}$ 是操作变量的列向量
• $\mathbf{t}$ 是目标图案的列向量

---

矩阵 $A$ 的特殊结构

1. 分块循环矩阵

由于环面拓扑的周期性和操作的局部性，$A$ 是一个分块循环矩阵（block circulant matrix）。

具体来说，如果将网格按行优先展开成一维向量，那么：

• $A$ 的每一行对应一个格子的方程
• 该行中，对应自身和四个邻居的位置为 1，其余为 0
• 由于周期性，这些 1 的位置模式在整行平移下重复出现

更精确地，$A$ 可以写成： $ A = I \otimes C + S \otimes I + S^{-1} \otimes I + I \otimes S + I \otimes S^{-1} $ 其中：

• $I$ 是 $N \times N$ 单位矩阵
• $S$ 是 $N \times N$ 的循环移位矩阵（$S_{i,i+1}=1$，$S_{N,1}=1$，其余为 0）
• $\otimes$ 表示 Kronecker 积
• 五项分别对应：自身、上、下、左、右的影响

2. 矩阵的对角化

循环矩阵可以在傅里叶基下对角化。因为 $S$ 的特征向量是离散傅里叶向量，特征值是 $N$ 次单位根。

设 $F$ 是 $N \times N$ 的离散傅里叶变换矩阵（在 $\mathbb{C}$ 中），则： $S = F \Lambda F^{-1}$ 其中 $\Lambda = \operatorname{diag}(1, \omega, \omega^2, \dots, \omega^{N-1})$，$\omega = e^{2\pi i / N}$。

由于 Kronecker 积的性质，$A$ 也可以在二维傅里叶基下对角化。

---

傅里叶变换解法

1. 二维傅里叶变换

定义二维 DFT： $ \hat{x}_{uv} = \sum_{i=0}^{N-1} \sum_{j=0}^{N-1} x_{ij} \omega^{iu + jv}, \quad \omega = e^{2\pi i / N} $ 同样定义 $\hat{t}_{uv}$。

2. 方程在频域的简化

在频域中，卷积变为乘积。操作的影响模式（自身+四邻）在频域的乘子为： $ \lambda_{uv} = 1 + \omega^{-u} + \omega^u + \omega^{-v} + \omega^v $ 因为：

• 自身贡献乘子 1
• 上移贡献 $\omega^{-u}$（时域移位对应频域相移）
• 下移贡献 $\omega^u$
• 左移贡献 $\omega^{-v}$
• 右移贡献 $\omega^v$

于是原方程组 $A\mathbf{x} = \mathbf{t}$ 在频域变为： $ \lambda_{uv} \hat{x}_{uv} = \hat{t}_{uv} \quad \text{对每个 } u,v $

3. 模 2 的注意事项

但我们的运算是模 2 的，而傅里叶变换在复数域。需要将问题转换到特征为 2 的域上。

由于 $N = 2^n$，在模 2 的世界里，$N \equiv 0$。实际上，在 $\mathbb{F}_2$ 上，$\omega$ 应理解为 $\mathbb{F}_{2^m}$ 中的本原 $N$ 次单位根（如果存在）。

更实际的做法：注意到 $\lambda_{uv}$ 可以具体计算。

---

$\lambda_{uv}$ 的具体计算

在复数域： $ \lambda_{uv} = 1 + 2\cos\left(\frac{2\pi u}{N}\right) + 2\cos\left(\frac{2\pi v}{N}\right) $ 因为 $\omega^u + \omega^{-u} = 2\cos(2\pi u/N)$。

关键观察：

由于 $N = 2^n$，$\cos(2\pi u/N)$ 是代数数，在模 2 下可能需要特殊处理。

但我们可以直接判断可解性：方程组有解当且仅当对每个 $(u,v)$，若 $\lambda_{uv} = 0$（在相应域中），则必须有 $\hat{t}_{uv} = 0$。

---

可解性分析

1. $\lambda_{uv}$ 何时为零？

在复数域，$\lambda_{uv}=0$ 当且仅当： $ \cos\left(\frac{2\pi u}{N}\right) + \cos\left(\frac{2\pi v}{N}\right) = -\frac{1}{2} $ 对于 $N=2^n$，$u,v \in \{0,1,\dots,N-1\}$。

由于余弦值是有理数的代数组合，$\lambda_{uv}=0$ 的情况相对稀少。

2. 在模 2 域中的对应

在 $\mathbb{F}_2$ 扩展域中，$\lambda_{uv}$ 可能为零。特别地：

• 当 $u=v=0$ 时，$\lambda_{00} = 1+1+1+1+1 = 5 \equiv 1 \pmod 2$（因为 5 mod 2 = 1）
• 当 $u=0, v=N/2$ 时，$\cos(\pi) = -1$，所以 $\lambda = 1+2+2(-1)=1+2-2=1$，模 2 为 1

实际上，对于 $N=2^n$，可以证明在 $\mathbb{F}_2$ 中，$\lambda_{uv}$ 对所有 $(u,v)$ 都不为零。这是因为： $ \lambda_{uv} \equiv 1 + (\omega^u+\omega^{-u}) + (\omega^v+\omega^{-v}) \pmod{2} $ 而在特征 2 的域中，$\omega^u+\omega^{-u}$ 的形式特殊。

3. 结论：总是有解

对于 $N=2^n$，可以证明矩阵 $A$ 在 $\mathbb{F}_2$ 上是可逆的。因此，对任意目标图案 $\mathbf{t}$，方程组 $A\mathbf{x}=\mathbf{t}$ 总有唯一解。

直觉理解：在 $2^n \times 2^n$ 的环面上，这种邻接模式形成的线性变换在模 2 下是非奇异的。

---

求解方法

由于 $A$ 可逆，我们可以直接解线性方程组。但 $N^2$ 最大约 $4\times 10^6$，直接高斯消元 $O((N^2)^3)$ 不可行。

1. 利用稀疏性

$A$ 每行只有 5 个非零元，是高度稀疏的。可以使用稀疏矩阵的高斯消元，但 $N^2$ 很大时仍可能太慢。

2. 二维 FFT 方法

在复数域解出 $\hat{x}_{uv} = \hat{t}_{uv} / \lambda_{uv}$，然后逆变换得到 $x_{ij}$，再取模 2。

但需要确保数值精度，因为 $N$ 可能很大（2048），FFT 在复数域计算后再模 2 可能因舍入误差出错。

3. 模 2 的 FFT

可以在 $\mathbb{F}_2$ 的扩展域上执行 FFT。由于 $N=2^n$，我们需要在 $\mathbb{F}_{2^m}$ 中找本原 $N$ 次单位根，其中 $m$ 足够大使得该单位根存在。

具体步骤：

1. 找到合适的扩域 $\mathbb{F}_{2^m}$ 包含本原 $N$ 次单位根 $\omega$
2. 在 $\mathbb{F}_{2^m}$ 中计算二维 DFT：$\hat{t}_{uv}$ 和 $\lambda_{uv}$
3. 计算 $\hat{x}_{uv} = \hat{t}_{uv} / \lambda_{uv}$
4. 逆 DFT 得到 $x_{ij} \in \mathbb{F}_{2^m}$
5. 由于解在 $\mathbb{F}_2$ 中，验证 $x_{ij} \in \{0,1\}$

这种方法复杂度 $O(N^2 \log N)$，可以处理 $n=11$ 的情况。

---

算法步骤总结

1. 输入与验证

• 读入 $n$，计算 $N = 2^n$
• 读入 $N \times N$ 的目标矩阵 $T$

2. 可解性判断（理论已证明总有解）

对于 $N=2^n$，问题总有解，无需判断无解。

3. 求解方程组

方法A（直接稀疏求解）：

• 构建稀疏矩阵 $A$（每行5个非零）
• 使用模2的高斯消元（位运算优化）
• 但 $N^2$ 太大时内存和时间可能不足

方法B（FFT-based）：

1. 选择扩域 $\mathbb{F}_{2^m}$，找到本原 $N$ 次单位根 $\omega$
2. 将 $T$ 视为 $\mathbb{F}_{2^m}$ 中的矩阵
3. 计算 $\hat{T} = \text{FFT2}(T)$
4. 计算乘子 $\lambda_{uv} = 1 + \omega^{-u}+\omega^u+\omega^{-v}+\omega^v$
5. 计算 $\hat{X}_{uv} = \hat{T}_{uv} / \lambda_{uv}$
6. 计算 $X = \text{IFFT2}(\hat{X})$
7. 取 $x_{ij} = X_{ij} \bmod 2$（由于在 $\mathbb{F}_2$ 扩展域中，实际上就是取0或1分量）

4. 输出

• 统计 $x_{ij}=1$ 的数量作为 $ans$
• 输出所有 $x_{ij}=1$ 的坐标 $(i,j)$

---

复杂度分析

• FFT2 复杂度：$O(N^2 \log N) = O(4^n \cdot n)$
• 对于 $n=11$，$N=2048$，$N^2=4,\!194,\!304$，$O(4^n \cdot n) \approx 4M \times 11 \approx 44M$ 次运算，可行
• 内存：$O(N^2)$，约 4M 个元素，每个元素在扩域中存储，内存可控

---

关键点与扩展思考

1. 为什么 $N$ 必须是 2 的幂？

• 保证了在 $\mathbb{F}_2$ 扩域中存在本原 $N$ 次单位根
• 使得 FFT 可以高效应用
• 矩阵 $A$ 可逆性依赖于 $N$ 是 2 的幂

2. 如果 $N$ 不是 2 的幂？

问题可能无解，且矩阵 $A$ 可能奇异。此时需要检查可解条件。

3. 实际实现细节

• 需要实现 $\mathbb{F}_{2^m}$ 上的算术运算
• 需要高效计算 $\lambda_{uv}$ 的逆
• 注意 FFT 的迭代实现以避免递归开销

4. 其他方法

• Meet-in-the-Middle：对于较小的 $n$，可以折半搜索
• 线性代数优化：利用矩阵的分块 Toeplitz 结构，使用循环卷积求解
• 观察模式：可能有闭合形式的解公式

---

总结

本题是一个经典的线性方程组在有限域上的求解问题，其特殊性在于：

1. 网格大小 $2^n$ 和环面拓扑带来了矩阵的循环结构
2. 模 2 运算使得傅里叶变换可以在特征 2 的域上进行
3. 对于 $2^n \times 2^n$ 的情况，问题总是有唯一解
4. 利用二维 FFT 可以在 $O(N^2 \log N)$ 时间内求解

关键在于认识到操作形成的线性变换在频域是对角化的，从而将大规模稀疏方程组转化为逐个频点上的标量方程。这种方法不仅高效，而且揭示了问题深层的代数结构。