QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#499689 | #7900. Gifts from Knowledge | Savior | WA | 0ms | 3592kb | C++20 | 2.1kb | 2024-07-31 17:05:52 | 2024-07-31 17:05:53 |
Judging History
answer
#include<bits/stdc++.h>
#define endl "\n"
using namespace std;
#define int long long
using ll=long long;
const int inf=1e9+7,N=50+5,mod=1e9+7;
typedef pair<int,int>P;
int qpow(int a,int b,int c){
int ans=1;
while(b){
if(b&1) ans=ans*a%c;
a=a*a%c,b>>=1;
}
return ans;
}
void solve(){
int r,c;
cin>>r>>c;
vector<vector<char>>s(r+1,vector<char>(c+1));
vector<int>cnt(c+1,0);
vector<vector<int>>e(2*r+1);
vector<vector<int>>tmp(c+1);
for(int i=1;i<=r;i++)
for(int j=1;j<=c;j++) {
cin >> s[i][j], cnt[j] += (s[i][j] == '1');
if(s[i][j]=='1') tmp[j].push_back(i);
}
for(int i=1;i<=c;i++){
if(cnt[i]+cnt[1+c-i]>=3){
cout<<0<<endl;
return;
}
if(2*i==1+c&&cnt[i]>=2){
cout<<0<<endl;
return;
}
}
for(int i=1;i<=r;i++){
for(int j=1;j<=c;j++){
if(s[i][j]=='1'){
for(auto &it:tmp[j]){
if(it==i) continue;
e[i].push_back(it+r);
e[i+r].push_back(it);
}
if(2*j==1+c) continue;
for(auto &it:tmp[1+c-j]){
if(it==i) continue;
e[i].push_back(it);
e[i+r].push_back(it+r);
}
}
}
}
vector<int>v(2*r+1,0);
int ans=1,num=0;
function<void(int)>dfs=[&](int u){
v[u]=num;
for(auto &it:e[u]){
if(v[it]) continue;
dfs(it);
}
};
for(int i=1;i<=2*r;i++){
if(!v[i]){
++num;
dfs(i);
ans=ans*2%mod;
}
}
for(int i=1;i<=r;i++){
if(v[i]==v[i+r]){
cout<<0<<endl;
return;
}
}
ans=ans*qpow(2,mod-2,mod)%mod;
cout<<ans<<endl;
return;
}
signed main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);cout.tie(nullptr);
int t=1;cin>>t;
while(t--)solve();
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 0ms
memory: 3592kb
input:
3 3 5 01100 10001 00010 2 1 1 1 2 3 001 001
output:
8 0 2
result:
wrong answer 1st numbers differ - expected: '4', found: '8'