cf1392 D. 505

题意：

给出一个 \(n \times m\) 的 01 矩阵，如果每个边长偶数的正方形子矩阵内 1 的个数都为奇数，则这是一个“好的”矩阵。如果能把矩阵改成“好的”，问最少改多少个位置

思路：

n和m都大于等于4就没答案，否则暴力枚举。

怎么枚举呢？n和m至少有一个小于4，状压dp就好了

const signed N = 1e6 + 3;
int n, m, a[N];

bool ok(int x) {
    for(int i = 1; i < m; i++) //只跟奇偶有关,所以异或一下
        if(!((x>>i&1)^(x>>(i-1)&1)))
            return 0;
    return 1;
}

signed main() {
    iofast;
    cin >> n >> m;
    if(n >= 4 && m >= 4) return cout << -1, 0;

    //把char[][]改成int[]
    for(int i = 0; i < n; i++)
        for(int j = 0; j < m; j++) {
            char c; cin >> c; if(c == '1')
                (n >= m ? a[i] |= (1<> f((1<(n,INF));
    for(int i = 0; i < (1<