我，牛子诗宝，代表博王国的荣耀。

FutaRimeWoawaSete · 2022-11-03 16:40:58 · 题解

sol of CF321D

我们凭感觉如果不是 m 的特殊限制，这是个不太可做的问题，所以从 m = \frac{n + 1}{2} 开始入手！！！1

考虑先从比较暴力地想法入手，设 c(x,y) 表示点 (x,y) 是否取反，即采用 0/1 表示。

我们发现在 m = \frac{n + 1}{2} 的意义下，存在以下两条限制：

动笔画画你就可以发现，任意一个子矩形覆盖到了第 x 行，一定覆盖 (x,y) 与 (x,y+m) 两者中的一个点，而且必定覆盖 c(x,m) 这个点，也就是同行的中点以及两边距离为中距的两个节点满足的关系。

反转一下看，列也满足这个性质。所以不管怎么覆盖每次总有两个变量一起变化，于是得到了上面的两条约束。

然后你还发现，子矩阵的操作是线性无关的，这是因为任何一个子矩阵操作不可能被表示成若干个其它子矩阵操作。

再进一步，我们发现对于 c 的取值，我们显然知道所有 c(x,y) 满足 1 \leq x,y\leq m 就可以还原出整个矩阵的 c，所以总的填发有 2 ^ {m \times m} 种，这不恰好对应了子矩阵操作的方案数 2 ^ {m \times m} 吗，所以确定 c 的过程和操作的过程是等价的。

后面的其实反而更简单一些，我们考虑先枚举第 m 列上前 m 行的 c，根据 c(i,m) \oplus c(m,m) \oplus c(i+m,m)=0 可以推出所有的 c(i+m,m) ，即第 m 列的情况。

然后你发现对于前 m - 1 列两两列之间元素它们是互相不影响的，因为它们之和第 m 列及以后的元素相关；同理，前 m - 1 行两两行的元素之间是互相不影响的，因为它们只和 m 行及以后的元素相关。

所以我们可以得出，在填 c 的意义下，若确定了第 m 行第 m 列的信息，前 m - 1 行/列之间的 c 是互相不影响的，这个结论在原来的子矩阵操作意义下一点也不显然。

当然第 m 行上即任意的 c(m,i) 之间也是互相不影响的。上面的式子也很好地说明了这一切，c(m,i) 仅与第 i 列的信息有关。

可以发现第 m 列和第 m 行的元素是信息量比较大的，我们考虑第 m 行的信息，由于两两是不互相影响的所以我们单独考虑每一个列，第 i 个列上先枚举 c(m,i)，然后依次枚举每一列上的所有元素后取 \max，得到了前 m 行/列的 c 即可还原整个矩形。

注意到在枚举完前 m - 1 行/列的每一个元素时可以得到其在限制中对应的剩下元素的 c 的情况，\max 应取这些元素的和。

时间复杂度 O(n ^ 2 2 ^ m)。

#include "bits/stdc++.h"
using namespace std;
const int Len = 36;
#define ll long long
#define int ll
const int Inf = 1e12;
int n,m,c[Len][Len],a[Len][Len];
#define v(x,y) (c[x][y] ? -a[x][y] : a[x][y])
inline int c3(int x,int y,int i)
{
    c[x][y] = i , c[x + m][y] = c[x][y] ^ c[m][y];
    c[x][y + m] = c[x][y] ^ c[x][m] , c[x + m][y + m] = c[x][y + m] ^ c[m][y + m];
    int mx = v(x , y) + v(x + m , y) + v(x , y + m) + v(x + m , y + m);
    return mx;
}
inline int c2(int y,int i)
{
    c[m][y] = i , c[m][y + m] = c[m][y] ^ c[m][m];
    int mx = v(m , y) + v(m , y + m);
    for(int i = 1 ; i < m ; i ++) mx += max(c3(i , y , 0) , c3(i , y , 1));
    return mx;
}
inline int c1()
{
    int mx = 0;
    for(int i = 1 ; i <= n ; i ++) mx += v(i , m);
    for(int i = 1 ; i < m ; i ++) mx += max(c2(i , 0) , c2(i , 1));
    return mx; 
}
ll ans = -Inf;
signed main()
{
    scanf("%lld",&n);for(int i = 1 ; i <= n ; i ++) for(int j = 1 ; j <= n ; j ++) scanf("%lld",&a[i][j]);
    m = (n + 1) / 2;
    for(int i = 0 ; i < (1 << m) ; i ++) 
    {
        for(int j = 1 ; j <= m ; j ++) c[j][m] = (i >> (j - 1)) & 1;
        for(int j = m + 1 ; j <= n ; j ++) c[j][m] = c[j - m][m] ^ c[m][m];
        ans = max(ans , c1());
    }
    printf("%lld\n",ans);
    return 0;   
}