QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#277250 | #7894. Many Many Heads | SSH# | RE | 0ms | 0kb | C++20 | 1.6kb | 2023-12-06 17:01:35 | 2023-12-06 17:01:35 |
Judging History
answer
#include <bits/stdc++.h>
#define int long long
using namespace std;
void solve();
signed main(){
cin.sync_with_stdio(0);
cin.tie(0);
int T = 1;
cin >> T;
while(T--){
solve();
}
return 0;
}
#define mod 1000000007
void solve(){
int n, m;
cin >> n >> m;
vector<int> cnt(m);
vector<vector<int>> g(n, vector<int>(m));
vector<vector<int>> pos(m);
vector<vector<array<int,2>>> G(n + 10);
for(int i = 0;i < n;i++){
for(int j = 0;j < m;j++){
char x;
cin >> x;
g[i][j] = x - '0';
if(g[i][j] == 1){
cnt[j]++;
pos[j].push_back(i);
}
}
}
for(int i = 0;i < m;i++){
if(i != m - i - 1){
if(cnt[i] + cnt[m - i - 1] > 2){
cout << "0\n";
return;
}
}
else{
if(cnt[i] > 1){
cout << "0\n";
return;
}
}
}
for(int i = 0;i < n;i++){
for(int j = 0;j < m;j++){
if(g[i][j] == 1){
for(auto k:pos[j]){
//dsu.merge(i + 1, k + 1);
G[i + 1].push_back({k + 1, 0});
}
for(auto k:pos[m - j - 1]){
//dsu.merge(i + 1, k + 1);
if(k != i)G[i + 1].push_back({k + 1, 1});
}
}
}
}
vector<int> vis(n + 10, -1);
function<bool(int)> dfs = [&](int u){
bool res = true;
for(auto& [v, w]:G[u]){
if(vis[v] != -1){
if(vis[v] != (vis[u] ^ w)){
return false;
}
}
else{
vis[v] = (vis[u] ^ w);
res |= dfs(v);
}
}
return res;
};
int ans = 1;
for(int i = 1;i <= n;i++){
if(vis[i] == -1){
vis[i] = 0;
if(dfs(i)){
ans *= 2;
ans %= mod;
}
else{
cout << "0\n";
return;
}
}
}
cout << ans << "\n";
}
詳細信息
Test #1:
score: 0
Runtime Error
input:
6 )) ((() [()] ()[()]() ([()]) ([])([])