vp了2023济南icpc，卡在一个典题上面（还是太菜了）。

题目链接：https://codeforces.com/gym/104901

直接说结论，给定一个无向图（无重边自环），每条边只能选择两个端点的其中一个，且必须选出一个，很显然对于其中一个连通块的选择方案只有 $2$ 种（第一个点选或者不选一旦确定，后面点的状态是固定的），所以总共的选择方案为 $2^{cnt}$ ， $cnt$ 为连通块的数量，当然前提是每个连通块都是二分图。

回到这个题，（设矩阵为 $m\times n$ ）当第 $i$ 列和第 $n-i+1$ 列 $1$ 的个数超过 $3$ 时无解，为 $1$ 时不需要连边，为 $2$ 时，若在同一行也不需要连，其他情况说明两个 $1$ 在不同的行，设为 $x,y$ ，有两种情况：

1.两个 $1$ 在同一列，说明两者必须一个反转，一个不反转

2.两个 $1$ 在不同列，说明两个必须同时不变，或者同时反转

设 $i$ 表示反转第 $i$ 行， $i+m$ 对应不翻转第 $i$ 行。

第一种情况，连 $x$ 和 $y$ 的边。

第二种情况，连 $x$ 和 $y+m$ 的边。

然后做二分图判定即可。

代码：

cpp
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ll long long
#define endl '\n'
const int M = 2e6 + 5;
const int inf = 2e9, mod = 1e9 + 7;
int a[M], b[M];
int vis[M];
string s[M];
vector<int> f[M];
void add(int x, int y)
{
    f[x].push_back(y);
    f[y].push_back(x);
    // cout<<x<<" "<<y<<endl;
}
int dfs(int x){
    for(auto to : f[x]){
        if(vis[to]){
            if(vis[x] == vis[to])return 0;
            continue;
        }
        vis[to] = 3-vis[x];
        if(!dfs(to))return 0;
    }
    return 1;
}
 void solve()
{
    int m, n;
    cin >> m >> n;
    for (int i = 1; i <= m; i++)
    {
        cin >> s[i];
        s[i] = " " + s[i];
    }
    vector<int> cnt(n + 2);
    vector<vector<int>> g(n + 2);
    for (int i = 1; i <= m; i++)
    {

        for (int j = 1; j <= n; j++)
            if (s[i][j] == '1')
            {
                cnt[j]++;
                g[j].push_back(i);
            }
    }
    for (int i = 1; i <= n; i++)
    {
        if (cnt[i] + cnt[n - i + 1] > 2)
        {
            cout << 0 << endl;
            return;
        }
    }
    for (int i = 1; i <= n / 2; i++)
    {
        if (cnt[i] + cnt[n - i + 1] == 2)
        {
            vector<int> v;
            for (auto x : g[i])
                v.push_back(x);
            for (auto x : g[n - i + 1])
                v.push_back(x);
            int x = v[0], y = v[1];
            if (x == y)
                continue;
            if (cnt[i] == 1)
            {
                add(x, y + m);
            }
            else
                add(x, y);
        }
    }
    for (int i = 1; i <= m; i++)
        add(i, i + m);
    int ans = 1;
    for (int i = 1; i <= 2 * m; i++)
    {
        if (!vis[i])
        {
            vis[i] = 1;
            if (!dfs(i))
                ans = 0;
            else
                ans = ans * 2 % mod;
        }
    }
    for (int i = 1; i <= 2 * m; ++i)
        vis[i] = 0, f[i].clear();
    cout << ans << endl;
}
signed main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int T = 1;
    cin >> T;
    while (T--)
    {
        solve();
    }
}