发现我们给一个点染上色后有：
我们称这是一个大小为 1 的十字。
进一步地，我们给这 5 个点再次染上色后有：
我们称这是一个大小为 2 的十字。
同理可得，我们给这 5 个点染上相同的大小为 2 的十字，可得一个大小为 4 的十字：
假设我们图的边长为 \(N=2^n\)，我们只需要染上一个大小为 \(w=\frac{N}{2}\) 的十字，左边的那一个点就会和右边的点抵消，上面的点就会和下面的点抵消。最终效果就是只染了一个点。
假如我们要染一个大小为 \(w=\frac{N}{2}\) 的十字，可以通过在这个十字的 5 个红色的点位染上 5 个大小为 \(\frac{w}{2}=\frac{N}{4}\) 的十字来实现：
同理，我们可以使用分治来实现这一过程，最后就只会需要染若干个大小为 1 的十字，这就是题目“绘画操作”的定义。
我们只需要对于每个需要染色的位置跑一遍分治即可。时间复杂度由 \(T(n)=5T(\frac{n}{2})+O(1)\) 得 \(O(N^2n^{\log_25})\)，期望得分 35。
#include <cstdio>
#include <cstdlib>
#include <set>
#define ll long long
#define N 3000
using namespace std;
ll n, siz;
ll a[N][N], v[N][N];
ll tot;
inline ll calc(ll x) {
return (x%siz+siz)%siz;
}
void fun(ll x, ll y, ll w) {
if(w == 1) {
v[x][y] ^= 1;
return;
}
fun(x, y, w/2);
fun(calc(x+w/2), y, w/2);
fun(calc(x-w/2), y, w/2);
fun(x, calc(y+w/2), w/2);
fun(x, calc(y-w/2), w/2);
}
int main() {
freopen("set.in", "r", stdin);
freopen("set.out", "w", stdout);
scanf("%lld", &n);
siz = 1<<n;
for(ll i = 0; i < siz; i++) {
for(ll j = 0; j < siz; j++) {
scanf("%lld", &a[i][j]);
}
}
for(ll i = 0; i < siz; i++) {
for(ll j = 0; j < siz; j++) {
if(a[i][j]) {
fun(i, j, siz / 2);
}
}
}
for(ll i = 0; i < siz; i++) {
for(ll j = 0; j < siz; j++) {
if(v[i][j]) {
tot++;
}
}
}
printf("%lld\n", tot);
for(ll i = 0; i < siz; i++) {
for(ll j = 0; j < siz; j++) {
if(v[i][j]) {
printf("%lld %lld\n", i, j);
}
}
}
}
考虑为什么会这么慢，因为一个点可能被染了多次，这可以被抵消，我们可以枚举 \(w\)，然后再同理得解。时间复杂度 \(O(N^2n)\)，期望 100。
不要开 long long。
#include <cstdio>
#include <cstdlib>
#include <set>
#define N 3000
using namespace std;
int n, siz;
bool a[N][N], v[N][N];
int tot;
inline int calc(int x) {
return (x % siz + siz) % siz;
}
inline int read() {
int x = 0;
char c = '.';
while(c < '0' || c > '9') c = getchar();
while(c >= '0' && c <= '9') {
x = (x << 1) + (x << 3) + (c ^ '0');
c = getchar();
}
return x;
}
void print(int x) {
if(x > 9) print(x / 10);
putchar(x % 10 + '0');
}
int main() {
freopen("set.in", "r", stdin);
freopen("set.out", "w", stdout);
n = read();
siz = 1<<n;
for(int i = 0; i < siz; i++) {
for(int j = 0; j < siz; j++) {
a[i][j] = read();
}
}
for(int w = siz/2; w >= 2; w /= 2) {
for(int i = 0; i < siz; i++) {
for(int j = 0; j < siz; j++) {
v[i][j] = 0;
}
}
for(int i = 0; i < siz; i++) {
for(int j = 0; j < siz; j++) {
if(a[i][j]) {
v[i][j] ^= 1;
v[calc(i+w/2)][j] ^= 1;
v[calc(i-w/2)][j] ^= 1;
v[i][calc(j+w/2)] ^= 1;
v[i][calc(j-w/2)] ^= 1;
}
}
}
for(int i = 0; i < siz; i++) {
for(int j = 0; j < siz; j++) {
a[i][j] = v[i][j];
}
}
}
for(int i = 0; i < siz; i++) {
for(int j = 0; j < siz; j++) {
if(v[i][j]) {
tot++;
}
}
}
print(tot);
putchar('\n');
for(int i = 0; i < siz; i++) {
for(int j = 0; j < siz; j++) {
if(v[i][j]) {
print(i);
putchar(' ');
print(j);
putchar('\n');
}
}
}
}