题解：CF1672G Cross Xor

· · 题解

CF1672G Cross Xor 题解

分三种情况考虑：

  1. > 可以证明，这种情况无论如何都可以变为全 0 矩阵。 > > 因为如果我们操作 $(x,y)$ 同一行同一列上的位置恰好一次，那么最后的结果就会是翻转 $(x, y)$。 因此答案就是 $2^{cnt_?}$。
  2. > 可以证明，这种情况只需要每一列的异或和相等就可以变为全 0 矩阵，如果是异或和是 1，不妨随便做一次操作变为异或和为 0。 > > 必要性：一次操作只能同时改变所有列的异或和。 > > 充分性： > > 如果我们操作 $(x,y)$ 同一行同一列上的位置恰好一次，那么最后的结果就会是翻转 $y$ 这一列上，除了 $(x, y)$ 以外的所有数。 > > 如果我们操作 $(x,y)$ 同一行同一列上的位置一次，$(z, y)$ 同一行同一列上的位置一次，最后的结果就是翻转 $(x, y)$ 和 $(z, y)$。 > > 所以，对于同一列，有偶数个 1，对于 $(x, y)$ 是 1，每次操作选取 $(x, y), (n, y)$。如果 $(n, y)$ 是 0，这会做偶数次，否则会做奇数次翻转，所以我们成功把一列消完了。 这种情况下，如果一列中有 $?$，那么，这一列异或和为 0,1 情况相等，计数是繁而不难的。
  3. > 可以证明，这种情况需要每一行，每一列的异或和均相等，如果是异或和是 1，不妨随便做一次操作变为异或和为 0。 > > 必要性：一次操作只能改变所有行列的异或和。 > > 充分性： > > 如果我们操作 $(a, b), (a, d), (c, b), (c, d)$，最后的结果是翻转 $(a, b), (a, d), (c, b), (c, d)$。 > > 所以，对于 $(a, b)$ 是 1，每次操作选取 $(a, b), (n, b), (a, m), (n, m)$。$(n, b), (a, m)$ 同上，每一行有偶数个 1，总共有偶数个 1，所以如果 $(n, m)$ 是 0，会做偶数次翻转 $(n, m)$，否则会做奇数次翻转，所以我们成功消完了。 假设所有行列异或和都是 0，都是 1 的情况差不多，因为对一个 $?$ 的取值对行列都有影响，所以行列连边形成了一个二分图，我们可以做的是翻转一条边两端的点值，每个点初始点值是：把 $?$ 视作 $0$ 的一行/列异或和。对于每个连通块，如果点值异或和为 0，取出一棵生成树做经典贪心，这样包可以消完，所以对非树边没有约束，答案就是 $2^{k}$，$k$ 是非树边个数。 
#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
#define int long long
#define x first
#define y second
using namespace std;
typedef pair<int, int> PII;
const int N = 4000 + 10, mod = 998244353;

int n, m, fa[N], sz[N], sze[N], sum[N];
int qmi(int a, int b) {
    int res = 1;
    while(b) {
        if(b & 1) res = res * a % mod;
        a = a * a % mod, b >>= 1;
    }
    return res;
}
int find(int x) {
    return fa[x] == x ? x : fa[x] = find(fa[x]);
}
void merge(int a, int b) {
    int x = find(a), y = find(b);
    if(x != y) fa[x] = y, sz[y] += sz[x], sze[y] += sze[x] + 1, sum[y] ^= sum[x];
    else sze[x] ++;
}
char g[N][N];
signed main() {
    ios::sync_with_stdio(0), cin.tie(0);
    cin >> n >> m;
    for(int i = 1; i <= n; i ++) for(int j = 1; j <= m; j ++)
        cin >> g[i][j];
    if(n % 2 == 0 && m % 2 == 0) {
        int ans = 1;
        for(int i = 1; i <= n; i ++) for(int j = 1; j <= m; j ++)
            if(g[i][j] == '?') ans = ans * 2 % mod;
        cout << ans << '\n';
    }
    else if(n % 2 && m % 2) {
        for(int i = 1; i <= n + m; i ++) fa[i] = i, sz[i] = 1, sze[i] = 0;
        for(int i = 1; i <= n; i ++) for(int j = 1; j <= m; j ++) if(g[i][j] == '1') sum[i] ^= 1, sum[j + n] ^= 1;
        for(int i = 1; i <= n; i ++) for(int j = 1; j <= m; j ++) if(g[i][j] == '?') merge(i, j + n);
        int cnt1 = 1, cnt0 = 1, ans = 1;
        for(int i = 1; i <= n + m; i ++)
            if(i == fa[i]) {
                if(sum[i]) cnt0 = 0;
                if(sum[i] != (sz[i] & 1)) cnt1 = 0;
                ans = ans * qmi(2, sze[i] - sz[i] + 1) % mod; 
            }
        cout << (cnt1 + cnt0) * ans % mod << '\n';
    }
    else {
        if(m & 1) {
            for(int i = 1; i <= max(n, m); i ++)
                for(int j = 1; j <= i; j ++) swap(g[i][j], g[j][i]);
            swap(n, m);
        }
        for(int i = 1; i <= n; i ++) for(int j = 1; j <= m; j ++) if(g[i][j] == '1') sum[j] ^= 1;
        for(int i = 1; i <= n; i ++) for(int j = 1; j <= m; j ++) if(g[i][j] == '?') sum[j] = min(-1ll, sum[j] - 1);
        int ans = 0;
        for(auto o : {0, 1}) {
            int cnt = 0;
            for(int j = 1; j <= m; j ++) if(sum[j] >= 0 && sum[j] != o) goto Saya;
            for(int j = 1; j <= m; j ++) if(sum[j] < 0) cnt -= sum[j] + 1;
            ans = (ans + qmi(2, cnt)) % mod;
            Saya: ;
        }
        cout << ans << '\n';
    }

    return 0;
}