QOJ.ac

QOJ

IDSubmission IDProblemHackerOwnerResultSubmit timeJudge time
#492#276847#7900. Gifts from Knowledgeucup-team956ucup-team956Failed.2023-12-07 13:32:312023-12-07 13:32:32

Details

Extra Test:

Accepted
time: 0ms
memory: 3888kb

input:

1
3 3
100
010
001

output:

4

result:

ok 1 number(s): "4"

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#276847#7900. Gifts from Knowledgeucup-team956#AC ✓55ms73416kbC++172.1kb2023-12-06 11:42:262023-12-06 11:42:26

answer

#include <bits/stdc++.h>
#define int long long
using namespace std;

int read() {int x; cin >> x; return x;}
const int mod = 1e9 + 7;


void solve() {
    int n = read(), m = read();
    vector a(n + 1, vector(m + 1, '0'));
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= m; j++) {
            cin >> a[i][j];
        }
    }

    vector<int>f(2 * n + 1), v(m + 1);
    for(int i = 1; i <= 2 * n; i++) {
        f[i] = i;
    }
    auto fi = [&](auto fi, int x) -> int {
        if(x != f[x]) f[x] = fi(fi, f[x]);
        return f[x];
    };
    auto merge = [&](int x, int y) -> void {
        int fx = fi(fi, x);
        int fy = fi(fi, y);
        if(fy != fx) f[fy] = fx;
    };
    int ans = 1, ok = 1, tot = 0;

    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= m; j++) {
            if(a[i][j] == '0') continue;
            else {
                int now = j, to = m - j + 1;
                if(v[now] == -1 || v[to] == -1) {
                    cout <<"0\n";
                    return;
                }
                if(v[now]) {
                    merge(v[now], i + n);
                    merge(v[now] + n, i);
                }
                if(v[to]) {
                    merge(v[to], i);
                    merge(v[to] + n, i + n);
                }
            }
        }
        for(int j = 1; j <= m; j++) {
            if(a[i][j] == '0') continue;
            if(v[j] == 0) v[j] = i;
            else v[j] = -1;
        }
    }
    for(int i = 1; i <= n; i++) {
        // cout << fi(fi, i) << " " << fi(fi, i + n) << "\n";
        if(fi(fi, i) == fi(fi, i + n)) {
            cout << "0\n";
            return;
        }
    }
    int cnt = 0;
    for(int i = 1; i <= 2 * n; i++) {
        if(fi(fi, i) == i) {
            cnt ++;
            if(cnt % 2 == 0) {
                ans = ans * 2 % mod;
            }
        }
    }
    cout << ans << "\n";
}

signed main() {
    ios::sync_with_stdio(false); 
    cin.tie(0) , cout.tie(0); 
    int t = read();
    while(t--) solve();
    return 0;
}