题解 - Luogu P10085 [GDKOI2024 提高组] 染色

简要题意

给定一个边长为 $2^n$ 的 01 循环矩阵，要求构造一组方案选出若干点，使得把每个点及其四个方向的邻点均翻转后，矩阵变为全 0。

解法

容易发现，一个点操作与不操作，可以只由它的上下左右四个点决定。

假设翻转与否由矩阵 $v$ 表示，且原矩阵 $w$ 有这样的子矩阵：

..h..
.icg.
jdabf
.kem.
..l..

就是，当前点是 $a$，周围一圈是 $b\sim e$，再往外一圈是 $f\sim m$。

则有

$$\begin{aligned}v_a &= w_a\oplus v_b\oplus v_c\oplus v_d\oplus v_e \\ &= w_a \\ &\oplus (w_b\oplus v_f\oplus v_g\oplus v_a\oplus v_m) \\ &\oplus (w_c\oplus v_g\oplus v_h\oplus v_i\oplus v_a) \\ &\oplus (w_d\oplus v_a\oplus v_i\oplus v_j\oplus v_k) \\ &\oplus (w_e\oplus v_m\oplus v_a\oplus v_k\oplus v_l) \\ &= w_a\oplus w_b\oplus w_c\oplus w_d\oplus w_e\oplus v_f\oplus v_h\oplus v_j\oplus v_l \end{aligned}$$

令 $w'_a=w_a\oplus w_b\oplus w_c\oplus w_d\oplus w_e$，那么只需要处理

..h..
.....
j.a.f
.....
..l..

的子问题即可。

因此，我们想到这样子的分治：

! ! ! ! 
 # # # #
! ! ! ! 
 # # # #
! ! ! ! 
 # # # #
! ! ! ! 
 # # # #

把整个矩阵像这样子染色，先转化 ! 和 # 的 $w$ 值，然后分别解决 ! 和 # 标识的两个子问题，然后再还原空格处的 $v$ 值。

关于分治的边界：当 $n=0$ 时，每个点自己解决自己，则 $v_a=w_a$。

令 $p=2^n$，则时间复杂度为 $T(p)=O(p^2)+2T(\frac{p}{2})=O(p^2)=O(2^{2n})$。

代码

#include <bits/stdc++.h>
using namespace std;

const int MXN = 1 << 11;
const int DIRs = 4;
const int Xs[] = {1, 0, -1, 0};
const int Ys[] = {0, 1, 0, -1};
int N, cnt;
bool mat[MXN][MXN];
inline int mv(int i, int p, int s) {
  int x(i + p * (1 << s));
  if (x < 0) x += (1 << N);
  if (x >= (1 << N)) x -= (1 << N);
  return x;
}
void solve(int x, int y, int s) {
  if (s == N) return;
  for (int i(0); i != (1 << (N - s)); ++i)
    for (int j(0); j != (1 << (N - s)); ++j)
      if (!((i + j) & 1)) {
        for (int d(0); d != DIRs; ++d)
          mat[mv(x, i, s)][mv(y, j, s)] ^= mat[mv(x, i + Xs[d], s)][mv(y, j + Ys[d], s)];
      }
  solve(x, y, s + 1);
  solve(x + (1 << s), y + (1 << s), s + 1);
  for (int i(0); i != (1 << (N - s)); ++i)
    for (int j(0); j != (1 << (N - s)); ++j)
      if ((i + j) & 1) {
        for (int d(0); d != DIRs; ++d)
          mat[mv(x, i, s)][mv(y, j, s)] ^= mat[mv(x, i + Xs[d], s)][mv(y, j + Ys[d], s)];
      }
}
int main() {
  cin >> N;
  for (int i(0), x(0); i != (1 << N); ++i)
    for (int j(0); j != (1 << N); ++j)
      cin >> x, mat[i][j] = x;
  solve(0, 0, 0);
  for (int i(0); i != (1 << N); ++i)
    for (int j(0); j != (1 << N); ++j) cnt += mat[i][j];
  cout << cnt << endl;
  for (int i(0); i != (1 << N); ++i) {
    for (int j(0); j != (1 << N); ++j)
      if (mat[i][j]) cout << i << ' ' << j << '\n';
    cout << flush;
  }
  return 0;
}