这道题被搞到模拟赛里去了，我显然没做出来。我一直在考虑的都是贪心策略或者动态规划，但是知道了正确解法后，再看 $n\leq 33$ 的数据范围，才觉自己的想法很可笑。

先说解法。既然数据范围小，但又不是那么小，那一定是和枚举有关，但又不用全枚举。而减少枚举次数就要看题中的特殊性质。数据范围是 $1000$ 似乎并没有什么用处，而 $m=\frac{n+1}2$ 以及 $n$ 为奇数则显得尤为特殊。$m=\frac{n+1}2$ 刚好比 $n$ 的一半大一些。不难注意到，如果矩阵覆盖到了第 $i$ 行，则 $a_{i, m}$ 一定会被覆盖到。进一步，$a_{i, j}, a_{i, j+m}(j<m)$ 中有且仅有一个位置被该矩阵覆盖到。设 $vis_{i, j}$ 表示 $a_{i, j}$ 是否取反，则 $vis_{i, j}\oplus vis_{i, m}\oplus vis_{i, j+m}=0(j<m)$。同理 $vis_{i, j}\oplus vis_{m, j} \oplus vis_{i+m, j}=0(j<m)$。这说明，如果知道了前 $m$ 行、前 $m$ 列是否反转，就可以知道整个矩阵的每个位置是否反转，则有 $2^{m^2}$ 种情况，这与直接枚举是否反转每个矩阵的情况总数相同，说明只要满足以上两个式子的矩阵都是合法的矩阵。观察这个式子，在知道了第 $m$ 行、第 $m$ 列的所有 $vis$ 值的情况下，被第 $m$ 行、$m$ 列所分成的四个区块中一个块内相邻的两个位置是没有关系的，每一个位置只和与其坐标相差 $m$ 的位置有关，所以只要把每个 $(i, j)(i, j<m)$ 和 $(i, j+m), (i+m, j), (i+m, j+m)$ 放一起计算贡献，其余都可以分开来。因此可以考虑令第一个式子中 $i=m$，则有 $vis_{m, j}\oplus vis_{m, m}\oplus vis_{m, j+m}=0$。此时去枚举第 $m$ 行的前 $1$ 至 $m$ 个位置的 $vis$ 值，就可以知道第 $m$ 行的全部 $vis$ 值。然后再观察第 $m$ 列，如果知道了第 $vis_{i, m}(i<m)$，就可以由 $vis_{i, m}\oplus vis_{m, m}\oplus vis_{i+m, m}=0$ 知道 $vis_{i+m, m}$ 的值。接着，对于第 $i$ 行的第 $j(j<m)$ 列，如果知道其 $vis$ 值，就容易知道 $vis_{i+m, j}, vis_{i, j+m}, vis_{i+m, j+m}$ 的值。则在 $O(2^m)$ 枚举完第 $m$ 行的前 $m$ 个位置，计算出整个第 $m$ 行后，就可以分别做每一行 $i(i<m)$，枚举 $vis_{i, m}$，再对于该行每一列 $j(j<m)$，分别枚举 $vis_{i, j}$，就知道 $vis_{i+m, j}, vis_{i, j+m}, vis_{i+m, j+m}$，一起计算 $a_{i, j}, a_{i+m, j}, a_{i, j+m}, a_{i+m, j+m}$ 的贡献，把枚举出每一组 $vis$ 的贡献计算出后求最大，然后累加起来即可。这样子是 $O(n^2)$ 的。因此总复杂度 $O(2^mn^2)$。具体实现见代码。

最后讲讲做完题后的思考。对于我最初的想法，显然是不现实的，应当尽早排除。而这题的教训就是在暴力枚举前务必观察性质，有些部分可以独立枚举的就分开来，于是大大降低了复杂度。