QOJ.ac
QOJ
ID | Submission ID | Problem | Hacker | Owner | Result | Submit time | Judge time |
---|---|---|---|---|---|---|---|
#492 | #276847 | #7900. Gifts from Knowledge | ucup-team956 | ucup-team956 | Failed. | 2023-12-07 13:32:31 | 2023-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"
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#276847 | #7900. Gifts from Knowledge | ucup-team956# | AC ✓ | 55ms | 73416kb | C++17 | 2.1kb | 2023-12-06 11:42:26 | 2023-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;
}