QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#499689#7900. Gifts from KnowledgeSaviorWA 0ms3592kbC++202.1kb2024-07-31 17:05:522024-07-31 17:05:53

Judging History

你现在查看的是最新测评结果

  • [2024-07-31 17:05:53]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3592kb
  • [2024-07-31 17:05:52]
  • 提交

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'