SP9534 JZPLIT - Turn on the lights 题解
FFTotoro
·
·
题解
前言
题解区全是 O\left(\frac{(n+m)^3}{w}\right) 的时间复杂度错误做法，还说这题卡常。这里提供一个 O(nm) 的做法。
解法
前置推导
下文中异或运算使用 \oplus 表示，乘法（仅考虑 0,1 时等价于与运算）使用 \otimes 表示。为方便后文叙述，在这里规定若干个矩阵 / 数列 / 常量：
- 矩阵 A：表示输入的矩阵，a_{i,j} 表示 (i,j) 上灯的初始状态；
- 矩阵 F：表示输出的矩阵（答案矩阵），f_{i,j} 表示 (i,j) 上的开关是否按下（1 表示按下，0 表示没有按下）；
- 数列 R(A)：R(A)_i=\bigoplus\limits_{j=1}^m a_{i,j}，即 A 的第 i 行所有元素的异或和；
- 数列 C(A)：C(A)_j=\bigoplus\limits_{i=1}^n a_{i,j}，即 A 的第 j 列所有元素的异或和；
- 数列 R(F)：R(F)_i=\bigoplus\limits_{j=1}^m f_{i,j}，即 F 的第 i 行所有元素的异或和；
- 数列 C(F)：C(F)_j=\bigoplus\limits_{i=1}^n f_{i,j}，即 F 的第 j 列所有元素的异或和；
- 常量 S(A)：S(A)=\bigoplus_{i=1}^n R(A)_i=\bigoplus_{j=1}^m C(A)_j，表示 A 中所有元素的异或和；
- 常量 S(F)：S(F)=\bigoplus_{i=1}^n R(F)_i=\bigoplus_{j=1}^m C(F)_j，表示 F 中所有元素的异或和；
由题意可得一个方程（这个方程是本题的核心）：
a_{i,j}=f_{i,j}\oplus R(F)_i\oplus C(F)_j
这个方程看起来很难处理，于是考虑对其进行变形。将 A 第 i 行的所有元素对应的方程求和，得到：
R(A)_i=R(F)_i\oplus(R(F)_i\otimes(m\bmod 2))\oplus S(F)
同理有：
C(A)_j=C(F)_j\oplus(C(F)_j\otimes(n\bmod 2))\oplus S(F)
发现这个式子与 n,m 的奇偶性有关，于是考虑分类讨论。
情况一：n,m 均为偶数
由上述推导出的方程可得：
R(A)_i=R(F)_i\oplus S(F)\\
C(A)_j=C(F)_j\oplus S(F)
于是只要确定 S(F) 即可推导出所有 R(F) 和 C(F)，进而确定所有 f_{i,j}。注意到一次操作会让 A 所有元素异或和的奇偶性变化（因为 n+m-1 为奇数），而在最后这个值会变为 0，故 S(F)=S(A)，可以直接求解 f_{i,j}。
情况二：n,m 其一为偶数
不妨设 n 为偶数。另一种情况是对称的。
此时的方程为：
R(A)_i=S(F)\\
C(A)_j=C(F)_j\oplus S(F)
::::info[证明]
现在只需要证明以下命题成立：
- 命题一：$\bigoplus\limits_{j=1}^mf'_{i,j}=R(F')_i$；
- 命题二：$\bigoplus\limits_{i=1}^nf'_{i,j}=C(F)_j$。
对于命题一，注意到初始时 $C(F)_j$ 和 $a_{i,j}$ 的值已知，意味着可以唯一确定 $R(F)_i\oplus f_{i,j}$ 的值，记为 $x_{i,j}$。分类讨论 $R(F)_i$ 的值可以推导出一个重要结论：不管 $R(F)_i$ 的值是什么，命题一成立的充要条件为 $x_{i,j}=1$ 的 $j$ 必有偶数个（重要依据是 $m$ 为奇数）。也就是说，这个命题成立与否与人为构造的 $R(F')$ 无关；又因为题目保证有解，所以命题一是天然满足的。
对于命题二，有：
$$
\begin{aligned}
C(F')_j&=\bigoplus\limits_{i=1}^nf'_{i,j}\\
&=\bigoplus\limits_{i=1}^n(a_{i,j}\oplus R(F')_i\oplus C(F)_j)\\
&=C(A)_j\oplus S(F)\\
&=C(F)_j
\end{aligned}
$$
故命题二成立。
::::
于是随便构造一组这样的 $R(F')$ 作为 $R(F)$ 即可。
### 情况三：$n,m$ 均为奇数
仍然尝试沿用上面的方程，可以得到：
$$
R(A)_i=S(F)\\
C(A)_j=S(F)
$$
这些方程似乎并不包含多少信息。尝试讨论 $S(F)$ 的取值：
- 若 $S(F)=0$，则 $A$ 所有行、列均包含偶数个 $1$。由此注意到一种构造：直接令 $F=A$ 就是正确的！因为 $a_{i,j}=1$ 的 $(i,j)$ 会被所有满足 $f_{i',j'}=a_{i',j'}=1(i=i'\lor j=j')$ 的开关分别翻转一次，而满足该条件的开关有奇数个（对应行列各有偶数个，扣掉中间算重的一个），符合要求；$a_{i,j}=0$ 的 $(i,j)$ 会被翻转偶数次（对应行列各有偶数个，但是没有被重复计算的），也符合要求；
- 若 $S(F)=1$，跟上一种情况同理，也令 $F=A$ 即可。
综上此时令 $F=A$ 即可。
## 实现
直接根据上面的结论构造 $R(F),C(F)$，进而构造 $F$。时间复杂度 $O(nm)$。
注意，对于代码中 $n,m$ 均为奇数的情况，因为只需要满足 $F=A$，所以直接假设了 $R(F),C(F)$ 均为 $0$；而实际上的 $R(F),C(F)$ 可能为 $1$。这仅仅是为了方便实现（最终导出的 $F$ 是正确的）。
```cpp
#include<bits/stdc++.h>
using namespace std;
int main(){
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
int n,m; cin>>n>>m;
vector<string> a(n);
for(auto &i:a)cin>>i;
vector<int> rs(n),cs(m);
// 对应文中的 R(A) / C(A)
for(int i=0;i<n;i++)
for(int j=0;j<m;j++)
rs[i]^=a[i][j]&1,cs[j]^=a[i][j]&1;
vector<int> r(n),c(m);
// 对应文中的 R(F) / C(F)
if(n&1){
if(!(m&1)){
int s=c[0]=cs[0]; // 使 sum C(F) 满足条件
for(int i=0;i<n;i++)
r[i]=rs[i]^s;
}
}
else{
if(m&1){
int s=r[0]=rs[0]; // 使 sum R(F) 满足条件
for(int j=0;j<m;j++)
c[j]=cs[j]^s;
}
else{
int s=accumulate(rs.begin(),rs.end(),0,bit_xor<>());
for(int i=0;i<n;i++)
r[i]=rs[i]^s;
for(int j=0;j<m;j++)
c[j]=cs[j]^s;
}
} // 分讨构造
for(int i=0;i<n;i++){
for(int j=0;j<m;j++)
a[i][j]^=r[i]^c[j];
cout<<a[i]<<'\n';
}
return 0;
}
```