QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#619932#7900. Gifts from Knowledgexjt05RE 22ms69308kbC++231.8kb2024-10-07 16:01:552024-10-07 16:01:56

Judging History

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

  • [2024-10-07 16:01:56]
  • 评测
  • 测评结果:RE
  • 用时:22ms
  • 内存:69308kb
  • [2024-10-07 16:01:55]
  • 提交

answer

#include<bits/stdc++.h>
#define test(i) cout << #i << " "<< i << " " << endl;
#define endl '\n'

using namespace std;
typedef long long ll;

const ll INF=0x3f3f3f3f;
const ll N=2e6+10;
const ll mod=1e9+7;

ll t,n,m;
string str[N];
ll a[N];
vector<ll> vis[N];

void fio(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
}

void init_set(int n){
	for(int i=0; i<=2*n+1; i++){
		a[i]=i;
	}
}

int find_set(int x){
	if(x != a[x]) a[x]=find_set(a[x]); //压缩路径
	return a[x];
}

void merge_set(int x, int y){
	x = find_set(x);
	y = find_set(y);
	if(x!=y) a[x]=y; //x以y为父
	
}

signed main()
{
	fio();
	cin >> t;
	while(t--){
		cin >> n >> m;
		init_set(n);
		for(int i=0; i<=m; i++){
			vis[i].clear();
		}
		for(int i=1; i<=n; i++){
			cin >> str[i];
		}
		//i是不翻,i+n翻
		ll flag=0;
		for(int i=1; i<=n; i++){
			for(int j=0; j<m; j++){
				if(str[i][j]=='1'){
					vis[j+1].push_back(i);
				}
			}
		}
		
		for(int i=1; i<=m; i++){
			//cout << vis[i].size() << endl;
			if(vis[i].size()+vis[m-i+1].size()>2){
				flag=1;
			}
			if(vis[i].size()==1){
				merge_set(vis[i][0],vis[m-i+1][0]);
				merge_set(vis[i][0]+n,vis[m-i+1][0]+n);
			}
			else if(vis[i].size()==2){
				merge_set(vis[i][0]+n,vis[i][1]);
				merge_set(vis[i][0],vis[i][1]+n);
			}
		}
		for(int i=1; i<=n; i++){
			//cout << i << " " << find_set(i) << " " << i+n << " " << find_set(i+n) << endl;
			if(find_set(i)==find_set(i+n)) flag=1;
		}
		if(flag){
			cout << 0 << endl;
			continue;
		}
		ll ans=1;
		ll cc=0;
		for(int i=1; i<=2*n; i++){
			if(a[i]==i){
				cc++;
			}
		}
		cc/=2;
		//cout << cc << endl;
		while(cc){
			cc--;
			ans%=mod;
			ans*=2;
			ans%=mod;
		}
		cout << ans%mod << endl;
	}
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 4ms
memory: 68356kb

input:

3
3 5
01100
10001
00010
2 1
1
1
2 3
001
001

output:

4
0
2

result:

ok 3 number(s): "4 0 2"

Test #2:

score: 0
Accepted
time: 22ms
memory: 69308kb

input:

15613
10 10
0000000000
0000000000
0000000000
0000000000
0000000000
0000000000
0000000000
0000000000
0000000000
0000000000
15 8
00000000
00000000
00000000
00000000
00000000
00000000
00000000
00000000
00000000
00000000
00000000
00000000
00000000
00000000
00000000
1 5
00000
5 9
000000000
000000000
0000...

output:

1024
32768
2
32
32768
128
32
16
16
2
16384
16384
128
128
32768
8192
128
64
16384
2
4
2
4096
16
4096
1024
32768
32768
16384
8
128
2
16
4096
8192
32768
8192
8192
16
16384
16384
256
128
8
256
8
4096
512
2
4
32
32
2
64
512
1024
32768
32768
2
64
16384
16
8192
16
256
16
64
8192
8192
64
1024
2
32768
2
4
51...

result:

ok 15613 numbers

Test #3:

score: -100
Runtime Error

input:

15759
9 6
000000
000000
000000
000000
000000
000000
000000
000000
000000
5 15
010000000000000
000000000000000
000000000000000
000100000000000
000100000000000
14 12
000000000000
000000000000
000000000000
000000000000
000000000000
000000000000
000000000000
000000000000
000000000000
000000000000
000000...

output:


result: